Prime Number stops after 29, but why?

This is a discussion on Prime Number stops after 29, but why? within the C Programming forums, part of the General Programming Boards category; This program I have written up has to print all the prime numbers between 1-10,000 However, for some reason, its ...

  1. #1
    The Nice Guy
    Join Date
    Sep 2004
    Posts
    19

    Prime Number stops after 29, but why?

    This program I have written up has to print all the prime numbers between 1-10,000 However, for some reason, its only prints out prime numbers up to 29.

    Code:
    #include <stdio.h>
    #include <math.h>
    #include <conio.h>
    
    int number, result, numerator;
    
    int primenum(int number)
    {
        numerator = (int)pow(2, number);
        
        return numerator;
    }    
    
    int main(void)
    {
        for(number = 1; number >= 0 && number <= 10000; number++)
        {
            //result = primenum(number);
            
            
            if(primenum(number) % number == 2)
            {
                printf("%d is a prime number\n", number);
            }
            
            //else
            
            //{
                //printf("%d is not a prime number\n", number);
            //}        
            
            //printf("%d square is %d\n", number, result);
        }
    getch();
    return 0;
    }
    Thanks in advance to anyone that could help rectify this problem.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,759
    pow() probably goes out of range after a while.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    probably because your algorithm sucks, pow(2, 29) is a large number, and as number grows it becomes even larger.
    :wq

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    Probably because you haven't implemented a prime number algorithm

    http://www.google.com/search?hl=en&l...osthenes+sieve
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    First your program doesn't verify prime numbers...
    Second pow(2, 33) doesn't fit in a int, much less 2^10000... only 2^32-1 for unsigned int, or -/+(2^31-1) for signed int, which are both 32 bits long.

    Third, I hope you don't mind a soiler....
    Code:
    #include<math.h>
    #include<stdio.h>
    
    int isprime(int n){
    	int end = (int)pow(n,0.5);
    	int i;
    	for(i=2;i<=end;i++){
    		if(0 == ( (n/i) - (n/(double)i) ) )
    			return 0;
    	}
    	return 1;
    }
    int main(){
    	int i;
    	printf("2\n");
    	for(i=3;i<=10000;i+=2){//pair numbers aren't prime
    		if(isprime(i))
    			printf("%d\n", i);
    	}
    	return 0;
    }
    Hope this helps...
    Last edited by xErath; 09-15-2004 at 09:17 AM.

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by xErath
    First your program doesn't verify prime numbers...
    Second pow(2, 33) doesn't fit in a int, much less 2^10000... only 2^32-1 for unsigned int, or -/+(2^31-1) for signed int, which are both 32 bits long.
    Unless of course you are on a machine that doesn't use 32 bit integers.

  7. #7
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    I am working on a seive method. I have one that works, but it is slower than it should. for the first 100,000 primes it takes 17.8 seconds.

  8. #8
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    the functions I posted calculate the 1st 100000 primes in about 2 seconds, with output, and less than 1 second without output, on my P4.

    The problem with the seive method is that it calculates all non-prime numbers, which are much more than primes.
    Last edited by xErath; 09-15-2004 at 12:33 PM.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by xErath
    the functions I posted calculate the 1st 100000 primes in about 2 seconds, with output, and less than 1 second without output.
    No it doesn't. You code does not give you "the first 100,000 primes". It gives you "the primes that are in between 3 and 10,0000". Big difference.

    Between three and tenthousand is not "the first one hundred thousand" primes.

    If you want really fast code, simply create a static list of the first N primes, and print it.
    Code:
    for( x = 0; x < numberofprimeswehaveinourlist; x++ )
        printf("%u", primes[x] );
    There, mine is the fastest. (Baring some faster output function, or simply printing a string containing all of the primes in one shot.)

    Quzah.
    Hope is the first step on the road to disappointment.

  10. #10
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    I think this:
    Code:
    for(i=3;i<=100000;i+=2){
    is editable... at least on my IDE... And It does it on those 2 seconds... with or without output only concerns commentimg the printf call

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    It still doesn't find "100000 primes". It finds the primes in the number range from N to X, which was what the point of my reply was. We like to be -pedantic here.

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    #include<xErath.h> xErath's Avatar
    Join Date
    Jun 2004
    Posts
    722
    Code:
    #define NPRIMES 100000
    
    int main(){
    	int i,k;
    	int primes[NPRIMES];
    	time_t ti, tf;
    	time(&ti);
    
    	primes[0] = 2;
    	for(i=3, k=1;k<NPRIMES;i+=2){//pair numbers aren't prime
    		if(isprime(i)){
    			primes[k++] = i;
    		}
    	}
    	time(&tf);
    
    	for(k=0;k<NPRIMES;k++)
    		printf("%d\n", primes[k]);
    	printf("t: %d\n", tf-ti);
    	return 0;
    }
    ...
    opps! my mistake...
    Now it's better....

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by xErath
    Now it's better....
    It is indeed better, but you again missed my point. You wording was incorrect. You stated it finds 100000 primes. This is not correct. Example:

    2, 3, 5, 7, 11

    The above are the first five primes, if you start at 2 and work up. The "first 100000" primes would be way way past the number 100,000, just like the fifth prime is past 5.

    The first hit on Google tells us that the 100000th prime is 1,299,709. However, that appears to be under debate because this link states that it is 2,395,021.

    I personally don't care what it is, but my point was you don't actually "find 100,000 primes".


    Quzah.
    Hope is the first step on the road to disappointment.

  14. #14
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    here is my prime number generator with sieve method. calculated the primes between 2 and 100,000 in 1.75 seconds with output
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int main (void){
            int *array;
            int x,y,input;
            int counter=1,element=0;
            clock_t start;
            clock_t end;
            array=malloc(2*sizeof(int));
            if(!array){
                    printf("Out of memory\n");
                    return EXIT_FAILURE;
            }
            array[0]=2;
            array[1]='\0';
            printf("Enter highest number to calculate\n>");
            scanf("%d",&input);
            printf("%d is prime\n",2);
            start=clock();
            for(x=3;x<input+1;x++){
                    for(y=array[0];;y=array[element]){
                            if(x%y==0){
                                    element=0;
                                    break;
                            }
                            if(element==counter-1){
                                    array=realloc(array,1*sizeof(int));
                                            if(!array){
                                                    printf("Out of Memory\n");
                                                    return EXIT_FAILURE;
                                            }
                                            array[counter]=x;
                                            counter++;
                                            array[counter]='\0';
                                    printf("%d is prime\n",x);
                                    element=0;
                                    break;
                            }
                            element++;
                    }
            }
            end=clock();
            printf("%f seconds\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
            free(array);
            return 0;
    }
    p.s. Is that the right way to free a dynamic array?
    Last edited by linuxdude; 09-17-2004 at 12:02 AM.

  15. #15
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Indeed it is correct to free() a dynamic array. However, the way you use realloc() is not recommended. You should instead have:

    Code:
    tmpPtr = realloc(array, 1*sizeof(int));
    
    if(!tmpPtr) {
      // do whatever
    } else
      array = tmpPtr;
    [edit]

    Your algorithm also seems flawed. I don't know if you have actually looked at some real prime number algorithms but they are actually quite extensive.

    Additionally, you don't need a dynamic array.

    [/edit]
    Last edited by master5001; 09-16-2004 at 10:38 PM.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. prime number.
    By tdoctasuess in forum C Programming
    Replies: 13
    Last Post: 05-13-2004, 08:03 AM
  2. Prime Factor Fxn
    By alpha in forum C++ Programming
    Replies: 2
    Last Post: 10-21-2003, 10:44 AM
  3. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM
  4. Replies: 3
    Last Post: 01-14-2003, 09:34 PM
  5. How is to check prime number?
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-04-2001, 11:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21