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.

pow() probably goes out of range after a while.

probably because your algorithm sucks, pow(2, 29) is a large number, and as number grows it becomes even larger.

Probably because you haven't implemented a prime number algorithm

http://www.google.com/search?hl=en&l...osthenes+sieve

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

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.

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.

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.

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.

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

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.

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

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.

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?

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]