Finding the largest Prime

[jeysel]

Hey guys, i need help about finding the largest prime.

Example:when i Input a number: 100
the output will be:The largest Prime number is 97.
Press any key to continue..

i have a codes but i dont think it is correct.

I need help...

[arcadiu]

Please post the code so we can see it and if you dont think its correct run the code to see if it works silly :P

Thanks

Arcadiu

[arun1390]

Here's a possible solution:

#include <iostream>
using namespace std;

int LargestPrime(int);

int LargestPrime(int TheNum)
{
	int FactorCount = 0;

	for (int i=TheNum; i>=2; --i)
	{

		for (int j=2; j<i; ++j)
		{
			if (i % j == 0)
			{
				++FactorCount;
			}
		}

		if (FactorCount == 0)
		{
			return i;
			break;
		}

		FactorCount = 0;
	}
	return 0;
}


int main()
{
	int Input, Result;
	cout << "Enter the number: ";
	cin >> Input;
	
	Result = LargestPrime(Input);

	cout << "The largest prime number before " << Input << " is " << Result << endl;
	
	return 0;
}

I've tested it with several positive integers and it works.
Try to understand what's happening. If you got any queries, post them and i'll try to answer.

[pet]

The function works very slowly for big numbers (1000000000).With little changes it works much more quickly.

int LargestPrime(int TheNum)
{
	int FactorCount = 0;

	for (int i=TheNum; i>=2; --i)
	{

		for (int j=2; j<sqrt(i) + 1; ++j)  // HERE
		{
			if (i % j == 0)
			{
		            ++FactorCount;
                            break;  // HERE
			}
		}

		if (FactorCount == 0)
		{
			return i;
			break;
		}

		FactorCount = 0;
	}
	return 0;
}

[jsmith]

Calculate sqrt(i) outside the for loop terminating condition so that it needs to be evaluated only once instead of sqrt(i) times. That will make it faster.

But why is everyone so interested in doing OP's homework assignment for him/her?

[arun1390]

I can understand why you put that break; part in the code, but i cannot figure out why you used square root. I guess it was to reduce the number of iterations, but i can't catch the logic behind that. Besides, the program does not work for small inputs, say 50.

[jsmith]

For all integers a and such that a * b = i and a <= b, it is easily shown that a <= sqrt( i ) and b >= sqrt( i ).
In fact, b = i / a, therefore all you need to do is find a.

[andrei c]

Hello jeysel!
All those function above, for what i've seen, don't return the maximum prime number, they just return 0 all the time.But there are very good besides this.Here's another way to do it:
1. first make a function that checks if a number is prime
2. then make a function that returns the maximum prime number smaller than N

i#include<iostream>

using namespace std;

bool Is_Prime(int Number) // function that checks if the number is prime
{
    int i = 2; // for iteration
    bool is_prime = 1; // the variable that says if number is prime or not
    float half = Number/2; // just so Number/2 wouldn't be calculated every iteration

    while( is_prime && i<=half ) // the while only makes max half iterations
    {
        if ( Number % i==0 )
          is_prime = 0;
        i++;
    }

    return is_prime; // returns 1 if it is prime and 0 if it isn't prime
}

int LargestPrime(int Number) // function that finds the maximum prime number smaller than Number
{
	int MaxPrime = 0; // variable that stores the max prime number that the function will return
	bool found_maxp = 0; // variable that keeps track if the max prime number has been found
	int i = Number;

	while ( !found_maxp && i>2 ) // the while only makes max number-2 iterations
	{
	    if ( Is_Prime(i) )
	    {
          found_maxp = 1; // the max prime number has been found, no need to search next iteration
	      MaxPrime = i; // the max prime number is of course i
	    }
        i--;
	}

	return MaxPrime; // returns the max prime smaller or equal to Number
}

int main()
{
    int Number=0; // the number for wich you want to find the max prime

    cout<<"Please enter the number"<<endl;
    cin>>Number;
    if( Is_Prime(Number) ) // the if can be taken out, it's just for test
      cout<<"The number is prime"<<endl;
    else cout<<"The number isn't prime"<<endl;
    cout<<"Max prime is "<<LargestPrime(Number); // this is the actual line that does the job

    return 0;
}

[jeysel]

hi andrei!

I am using dev-c++ application.
I tested it and it will not run.

I will try make one code of this. I will send it.

[andrei c]

It must run. I've compiled myself and tested it before sending it to you.I use the CodeBlocks IDE and the GCC compiler and it works.

[andrei c]

OOO !!!
I know what the mistake is.
It's actually the first line:

i#include<iostream> 

As you can see i.ve put an 'i' before #include<iostream>. The compiler doesn't know what 'i' is.Sorry.

[jeysel]

tnx for the advice. I have solve it..thanks guys..