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 !!!

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.

I was trying to implement

The Sieve of Eratosthenes

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.

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/

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.

Ok! Ok! I will!

Can you help me with my above code ???

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

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

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;
}

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;
}

Thank you all for such good replies !!!

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);
}

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.