# Generating Primes !?!?!?!

• 03-12-2003
Moni
Generating Primes !?!?!?!
I was trying to code which will generate primes. But what is wrong in my code? why it's not working !

Code:

```  #include<iostream.h> #include<math.h> void primes(long n) {   const np = 100;   long mult[np],P[np],i,j,limit = sqrt(n),plimsq,rootn,dx,x;   bool prime;   P[1] = 2;   P[2] = 3;   P[3] = 5;   i = 3;   if(n < 5)   {       for(j=1;j<=((n+1)/2);++j)         cout << P[j];   }   else   {       for(j=1;j<=3;++j)         cout << P[j];       x = 5;       plimsq = 25;       limit = 3;       dx = 2;       rootn = sqrt(n);       while(x<n)       {         x += dx;         dx = abs(dx-6);         if(limit <= i)         {             if(x >= plimsq)             {               mult[limit] = plimsq;               limit++;               if(limit <= i)                   plimsq = P[limit]*P[limit];             }             prime = true;             j = 3;             while(prime = true && j < limit)             {               while(mult[j] < x)               {                   mult[j]+=P[j]*2;                   prime = (x != mult[j]);                   j++;               }               if(prime)               {                   cout << x;                   if(x <= rootn)                   {                     i++;                     P[i] = x;                   }               }             }         }       }   } } int main() {   cout << " Now see the primes : " << endl;   primes(20);   cin.get();   return 0; } ```
If you know better algorithms than this one let me know. If code of that algo. is included that will be really nice !!!
• 03-12-2003
Shiro
A very simple algorithm to check if a certain number N is prime or not would be to let a variable P run from 2 until sqrt(N) and then check if N mod P is equal to 0. If N mod P is 0, then this means that P is a divisor of N and N is not a prime number.

You could add that algorithm in a while loop from for example 1 to M, where M is the maximum number and check for each number between 1 and M if it is prime or not.

As far as I know there are no real prime generating functions.
• 03-12-2003
Moni
I was trying to implement

The Sieve of Eratosthenes
• 03-12-2003
pianorain
Quote:

Originally posted by Shiro
As far as I know there are no real prime generating functions.
Yup, you're right. The algorithm you described is more effiecent than the Sieve of Eratosthenes by a pretty good amount.
• 03-12-2003
Moni

Yes! it is fast for instant primality test but if I want to store primes in memory for random access (required by another program most oftenly) then the Sieve of Eratosthenes is best. Agree ???

Look:

http://www.bagley.org/~doug/shootout/bench/sieve/

• 03-12-2003
XSquared
Please just stick with the default font. Your posts are hurting my eyes.

For generating prime numbers, I think that the sieve would be faster than Shiro's method.
• 03-12-2003
Moni
Ok! Ok! I will!

Can you help me with my above code ???
• 03-14-2003
Moni
Hello! Still I don't know where is my mistake !

Have any good code to gen. primes ?????????
• 03-15-2003
JamesMI
This seems to work, i checked the number of primes up to 100, 1000, 10000 against a list I found on the internet and seems to check out ok. I am in now way an expierienced programmer, so I am sure it can be cleaned up.

Anyway, here it is...
Hope it helps

Code:

```#include <iostream> int main() {         int maxn = 0;        //Max number of integers to go through         int curn = 0;        //Current modulus         int nprimes = 1;    //number of prime numbers found         cout << "Enter maximum number: ";         cin >> maxn;         cout << endl;         if(maxn%2 != 0)                //If max n is odd add 1 so there is no remainder                 maxn++;                //  in the next calculation         int prime[maxn/2 - 1];         for(int x = 1 ; x < (maxn/2); x++)              //Make a list of all odd integers between         {                                                      //  3 and maxn, inclusive.                 prime[x-1] = 2*x + 1;                  //  There is no need to check evens.         }         for(int y = 0; y < maxn/2-2; y++)         {                 for(int x = 0; x < maxn/2-2-y; x++)                 {                         if(curn == 0)                                 curn = prime[y];                         if(curn != 0)                                 if(prime[x+y+1] % curn == 0)                                         prime[x+y+1] = 0;              //if divisible by curn then its                 }                                                              //  not prime, set to 0.                 curn = 0;         }         cout << 2 << endl;              //didn't test for 2 because no need to check evens         for (int x = 0 ; x < maxn/2-1; x++)         {                 if(prime[x] != 0)              //only print the primes, if its 0 it's not prime                 {                         cout << prime[x] << endl;                         nprimes++;                 }         }         cout << endl << "The total number of primes found is " << nprimes << endl;         return 0; }```
• 03-15-2003
JamesMI
After I posted that, I realized I could make it a little faster by not checking numbers divisble by 3. I'll try to make the change and repost it.

I realize it's not quite what you want because you cant tell it how many primes you want, but I haven't figured that part out yet. I tested this for the numbers between 2 and 1,000,000, and it checks out with what I found online. It did take 5 to 10 minutes to find the primes up to 1,000,000. This is on a celeron 366 though.

Ok Here is the revised version...

Code:

``` #include <iostream> int main() {         int maxn = 0;         int max = 0;         int toggle = 0;                        //used to toggle between 2 and 4, faster than raising 1 to a power.         int nprimes = 0;                        //number of primes found                 cout << "Enter maximum number: ";         cin >> max;         cout << endl;         maxn = max;                 if(maxn%3 != 0)                 maxn = (maxn  - maxn%3);          //Make maxn divisible by 3.         maxn = maxn/3;                                //Only checking 1/3 of the numbers         int pprimes[maxn];                        //create an array to hold possible primes.         pprimes[0] = 5;                                //start checking with number 5.         for(int x = 1; x < maxn; x++)                //This for loop fills an array with integers starting with 5         {                                                //that are not divisible by 2 or 3.                 if(toggle)                 {                         pprimes[x] = pprimes[x-1] + 4;                         toggle = 0;                 }                 else                 {                         pprimes[x] = pprimes[x-1] + 2;                         toggle = 1;                 }         }                 for(int y = 0; y < (maxn-1); y++)         {                 if(pprimes[y] != 0)                 {                 for(int x = 0; x < (maxn-2-y); x++)                 {                         if(pprimes[x+y+1] != 0)                                 if(pprimes[x+y+1] % pprimes[y] == 0)                                         pprimes[x+y+1] = 0;                 }                 }         }         if(pprimes[maxn-1] > max)  //If i found 1 prime to many dont display it                 maxn--;                 cout << 2 << endl;        // 2 and 3 we know are prime, we started testing at 5         cout << 3 << endl;                 for(int x = 0; x < maxn; x++)         {                 if(pprimes[x] != 0)                 {                         cout << pprimes[x] << endl;                         nprimes++;                 }         }                 cout << "The total number of primes found = " << nprimes+2 << endl; }```
• 03-15-2003
Moni
Thank you all for such good replies !!!
• 03-16-2003
JamesMI
After doing a quick search on google, I found an example in c for finding primes that is much faster than the one I wrote. It can easily be converted to c++ or you can check the authors example in c++ on his site. I found the primes between 2 and 1,000,000 in less than 2 seconds on my 366 celeron, the original code I wrote took over 5 minutes. I modified it slightly from it's original version, I left the original header in place to provide due credit to the author.

Code:

```/* -*- mode: c -*-  * \$Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp \$  * http://www.bagley.org/~doug/shootout/  */ #include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) {     int NUM = ((argc == 2) ? atoi(argv[1]) : 1);     static char flags[1000000 + 1];     long x, i, k;     int count = 0;     while (NUM--) {         count = 0;         for (i=2; i <= 1000000; i++) {             flags[i] = 1;         }         for (i=2; i <= 1000000; i++) {             if (flags[i]) {                 // remove all multiples of prime: i                 for (k=i+i; k <= 1000000; k+=i) {                     flags[k] = 0;                 }                 count++;             }         }     }     printf("Count: %d\n", count);     // Now list the primes     for (x=0; x < 1000000; x++)             if(flags[x]){                     printf("  %d",x);     return(0); }```
• 03-16-2003
XSquared
Code:

`static char flags[1000000 + 1];`
It would probably be safer to use dynamic memory allocation for this so you don't run out of stack space.