Program that determines if a number is prime

[dark7angelx07]

Hi,
I need help writing a function that determines if a number is prime. It has to print all the prime numbers between 1 and 10000
this is what i have...where i put a " */* " is where i need your help.....

#include<iostream>

using std::cout;
using std::endl;

#include<iomanip>

using std::setw;

[U]/* write prototype for function prime */[/U]

int main()
{
  int count = 0;

  cout << "The prime numbers from 1 to 10000 are:\n";

  for (int loop =2; loop <= 10000; ++loop)

     if ( [U]/* make call to function prime */ [/U] ) {
        ++count;
        cout << setw( 6 ) << loop;

     if ( count % 10 == 0)
        cout << '\n';
}

  cout << '\n' << "There were " << count
         << " prime numbers\n";

 return 0;
}
  bool prime (int n)
{
  for ( int i = 2; [U]/*write loop condition */[/U]; i++ )

     if( [U]/*write code to test if n is divisible by i */[/U])
        return false;

   return true;
}

<< moderator edit: added [code][/code] tags >>

I need all the help i can get ;)

[zyruz]

to call the function prime, it is just to add:
prime(loop)

a simple loop condiction is:
(n/2)+1 > i
since after 1/2 of the val of n there cant be a fraction of the n number.

and the test are simple ennuf:
if (n%i == 0)

[Rashakil Fol]

To find if a number n is prime, you can just loop through all the numbers from 2 to (n - 1) and see if any of them divide evenly, using the modulus operator. So your loop ending condition could be (i < n), and you know that i divides into n if (n % i) equals 0.

This is a dumb algorithm, though. Instead, you can loop through all the numbers from 2 to the square root of n and test them. No need to go all the way up to (n - 1). Because if a number more than the square root of n divides into n, then a number less than the square root of n also works.

You might also want to try figuring out a method that doesn't use a prime testing function, which uses an array (maybe some other time).

Making the call to the function prime would be the same as making any function call, would it not? prime(loop).

[murschech]

Someone commented that to see if n is a prime you only have to check possible divisors < sqrt(n). In addition, you can decrease the computing time a lot by testing the divisor 2 , then 3, 5, 7..., skipping every other integer. The reason that this works is once you've determined that 2 is not a divisor you don't have to check 4, 6,8...or any even integer because if one of them were a divisor then so would 2 be a divisor. With a little ingenuity you can extend this to not testing multiples of 3 once you've determined that 3 is not a divisor, etc.

Actually, to produce a table of all the primes < 100000 (or, for that matter, of 1 million or ten million) there's a much better way called the sieve of Eritosthenes. (I think I spelled that all wrong). You can find it in many books. It's blindingly fast, using no divisions and a short code does the trick. Maybe this is what your instructor really wanted.

[WolfPack]

I think I read somewhere that to find out if a number is a prime, you dont have to check dividing upto n-1. Upto squareroot(n) is enough. check it out.

[cpp noob]

i got a similar program too :

# include<iostream.h>
# include<conio.h>

void main()

{
	clrscr();

	int isprime(int);
	int value;

	//input
	cout<<"Enter a number to verify whether it is prime or not "<<endl;
	cout<<"Enter -1 to stop"<<endl;
	cin>>value;

	//output
	while (value!=-1)
		{

		if (isprime(value)==1)
			{
			cout<<"Yes the number is prime"<<endl;
			}
		else
			{
			cout<<"Sorry, not a prime"<<endl;
			}
		getch();
		clrscr();
		cout<<"Enter a number to verify whether it is prime or not "<<endl;
		cin>>value;

		}
}

	//calculation
	int isprime(int valuex)
		{
		int x,j;
		x=1;

		for (j=2 ; j<valuex/2 ; j++)
			{
			if ((valuex%j)==0) x=0;
			}

		if(x!=0) return 1;
		else return 0;
		}

<< moderator edit: added [code][/code] tags >>

:lol:
created on 6/25/2005

[dark7angelx07]

Hi , I had a question again for what you said above.....

So I would just write..... if prime(loop) ...Is that how I should write it??
OR if (prime(loop)) ???

What should I write for the prototype for function prime? (first line)

Thank you so much for helping me.....

[murschech]

Your program doesn't make use of the efficiencies I mentioned. For one thing, you test possible factors up to valuex/2 but you only have to go up to sqrt(valuex), which is much smaller. (For example, sqrt(100) is 10, much less that 100/2.) Also you increment trial divisors by one rather than 2. Finally, once you find a divisor (and so, you know the number's not a prime), you contiinue to try more divisors!

Here's my version.

#include <iostream>
using namespace std;

bool isaprime(long);

bool isaprime(long x)
{   long n;
    // is 2 a divisor?
    if ( x%2 == 0)
       return false;
    n = 3;
    while (n*n <=x)
    {   if (x%n == 0)
           return false;
        n += 2;
    }
    return true;
}

int main()
{   long x;
    while (1)
    {   cout <<"Enter a positive integer to check for primality, 0 to exit: ";
        cin >> x;
        if (x == 0)
        {   cout << "Thanks for the fun. Come again.\n";
            return 1;
        }
        if (isaprime(x))
           cout <<x<<" is a prime\n";
        else
           cout <<x<<" is not a prime\n";

   }

}

<< moderator edit: fixed [code][/code] tags (forward slash) >>

[mina1984]

cpp noob
using your program, which tests for the integer input by the user,
how you could test all the numbers from 1 to 10,000? I duno i was all curious about it too.
:)
Mina

[cpp noob]

i lucky have this program creted on the same day

# include<iostream.h>
# include<conio.h>

void main()

{
    clrscr();
    int value, x, i, j;

    //input
    cout<<"Enter the value to which you want to find the prime numbers ";
    cin>>value;

    //calculation
    for ( i=3 ; i<=value ; i++)
        {
        x=1;

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

    //output
        if(x!=0) cout<<i<<" is a prime number"<<endl;
        }
    getch();
}

[dark7angelx07]

Here are the correct codes:

/* write prototype for function prime */ = bool prime(int n);

if ( /* make call to function prime */ ) = if (prime(loop))

for ( int i = 2; /*write loop condition */; i++ )
=
for ( int i = 2; (n/2) + 1 > i; i++ )

if( /*write code to test if n is divisible by i */)
=
if( n%i == 0 )

[zyruz]

this is a prime tester that uses the advises from post's here.

bool prime(int num)
{
    // all numbers from 1 and lower aint primes.
    if(num <= 1)
    {
         return false;
    }
    // 2 is a prime.
    if(num == 2)
    {
         return true;
    }
    // is 2 a divisor?
    if ( num%2 == 0)
    {
       return false;
    }
    
    for (int n=3;n*n <= num;n+=2)
    {   if (num%n == 0)
           return false;
    }
    // done testing, so return it as prime.
    return true;
}

[sowmya588]

to check if a number is prime ,u could simply check if the number equals (6x+ or - 1) for any x

[TheBeast32]

I have made someyhing like this before.
Here it is:

bool CheckPrime(unsigned long num)
{
     unsigned long long int x = 2;
     bool prime;
     
     if (num < 4)
     {
     switch (num)
     {
     case 1:
     prime = false;
     break;
     
     case 2:
     prime = true;
     break;
     
     case 3:
     prime = true;
     break;
     
     case 4:
     prime = false;
     break;
     }
     }
     
     else
     {
while (x < (num / 2) + 1)
{
      if (num % x == 0)
      {
      prime = false;
      break;
      }
      else 
      {
      prime = true;
      x++;
      }
}
      }

return prime;
}

[Dave Sinkula]

If num < 4, how will it ever be equal to 4 for the switch? Might you have meant 0?

[Yaka]

hey, could any one find the error in this program please. i wrote the thing but theres sumthing wrong with it. :(..thank you

#include <iostream>
#include <math.h>

#define TRUE 1;
#define FALSE 0;

int main()
{
   int number;

   getNumber(*number);

   if (isPrine(number)) 
      cout << "\n" << number << is a prime number\n";
   else 
      cout << "\n" << number << is not a prime number\n";

   return 0;
}

void getNumber(int &number)
{
   cout << "Please enter a positive number ";
   cin >> number;
   if (!cin.good())
   {
      printf("Invalid number entered\n");
      exit(1);
   }
}

int isPrime(int number)
{
   int count, s;

   /* Every even number is not prime */
   if (number % 2 == 0) return TRUE;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0) return TRUE;
   }
   return FALSE;
}

[dougy83]

getNumber(*number); this is wrong. Get rid of the *, as you are passing it by reference. if (isPrine(number)) should be spelt correctly

you will have to declare your functions before the main() routine, so put:

void getNumber(int &number);
isPrime(number);

on the line before main()

As an aside, why is checking division against every odd number the best way to do it? I would have thought it would be quicker to test division against every prime number less than sqrt(number)... Obviously if a number is not divisible by e.g. 5 (prime), it won't be divisible by any multiple of 5 (which obviously won't be prime).

[vmanes]

And the number 1 thing wrong with it is that the test function returns TRUE for non-primes and FALSE for primes!!!

Why the #define TRUE and FALSE when C++ has the perfectly good built in bool type, with values true and false ?

ps - you're responding/reopening a three year old thread, that saw a rebirth three weeks ago. Wasn't there enough discussion for you to find what you needed?

[terminator0031]

THE ULTIMATE SOLUTION IS THIS

Just change 100 to wherever you want it to stop.

Posted by James. :icon_cool:

#include "iostream"
#include "cstdlib"
#include "cmath"

using namespace std;




//Determines the prime numbers in a loop from 2 to 100
int main () {


int p_number;



for ( p_number = 2; p_number <= 100; p_number++)

{  
	if (p_number == 2) {cout << "2 is prime\n";}
    if (p_number == 3) {cout << "3 is prime\n";}
 if (p_number == 5) {cout << "5 is prime\n";}
if (p_number == 7) {cout << "7 is prime\n";}
	if((p_number % 2) != 0){ 
		
		if((p_number % 3) != 0){
		
			if((p_number % 5) != 0){
              if((p_number % 7) != 0){
				  if((p_number % 9) != 0){
			cout << p_number << " is prime\n";
				  }
			  }
			}
		}
}

}

system ("PAUSE");


return 0; 

}

[WaltP]

THE ULTIMATE SOLUTION IS THIS

Only if you can't program... :icon_rolleyes:

[DavidB]

Actually, to produce a table of all the primes < 100000 (or, for that matter, of 1 million or ten million) there's a much better way called the sieve of Eritosthenes. (I think I spelled that all wrong). You can find it in many books. It's blindingly fast, using no divisions and a short code does the trick. Maybe this is what your instructor really wanted.

The Sieve of Erastothenes:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://mathworld.wolfram.com/SieveofEratosthenes.html

The Wikipedia page includes pseudocode.