1. ## 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 !!!

2. 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.

3. I was trying to implement

The Sieve of Eratosthenes

4. 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.

5. 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/

6. 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.

7. Ok! Ok! I will!

Can you help me with my above code ???

8. Hello! Still I don't know where is my mistake !

Have any good code to gen. primes ?????????

9. 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;
}```

10. 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;
}```

11. Thank you all for such good replies !!!

12. 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);
}```

13. 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.