Thread: Generating Primes !?!?!?!

  1. #1
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104

    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 !!!
    Last edited by Moni; 03-12-2003 at 12:40 PM.
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  2. #2
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    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. #3
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    I was trying to implement

    The Sieve of Eratosthenes
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  4. #4
    Anti-Poster
    Join Date
    Feb 2002
    Posts
    1,401
    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.
    If I did your homework for you, then you might pass your class without learning how to write a program like this. Then you might graduate and get your degree without learning how to write a program like this. You might become a professional programmer without knowing how to write a program like this. Someday you might work on a project with me without knowing how to write a program like this. Then I would have to do you serious bodily harm. - Jack Klein

  5. #5
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104

    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/

    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  6. #6
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Last edited by XSquared; 03-12-2003 at 01:20 PM.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  7. #7
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Ok! Ok! I will!

    Can you help me with my above code ???
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  8. #8
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Hello! Still I don't know where is my mistake !

    Have any good code to gen. primes ?????????
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  9. #9
    Registered User
    Join Date
    Jan 2003
    Posts
    16
    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. #10
    Registered User
    Join Date
    Jan 2003
    Posts
    16
    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;
    }
    Last edited by JamesMI; 03-15-2003 at 08:51 AM.

  11. #11
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Thank you all for such good replies !!!
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  12. #12
    Registered User
    Join Date
    Jan 2003
    Posts
    16
    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. #13
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding primes
    By scwizzo in forum C++ Programming
    Replies: 11
    Last Post: 09-10-2008, 06:15 PM
  2. Doxygen failing
    By Elysia in forum A Brief History of Cprogramming.com
    Replies: 19
    Last Post: 04-16-2008, 01:24 PM
  3. primes program need some help
    By Mshock in forum C Programming
    Replies: 2
    Last Post: 04-17-2006, 07:21 PM
  4. a program that writes the primes
    By Geo-Fry in forum C++ Programming
    Replies: 8
    Last Post: 03-29-2003, 06:37 PM
  5. primes
    By godfather in forum C++ Programming
    Replies: 3
    Last Post: 05-08-2002, 01:44 PM