# Prime Number stops after 29, but why?

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 09-16-2004
linuxdude
my algorithm is fine. I checked my primes and they are all prime. I forot about that temp pointer for the return value of realloc, but it isn't needed. If it can't allocate it'll exit so it doesn't matter. It wouldn't be able to calculate any higher anyway. Why don't I need I a dynamic array? I need an array to have all the prime numbers so far and I don't know how many I have so what do you suggest just guess?
• 09-17-2004
Thantos
Only thing is that if realloc() fails you still haven't freed the old area in memeory. Also its good practice not to increase the size by one everytime but to double it when you need more. Its a small change out of memory to run time.
• 09-17-2004
kermit
Quote:

Originally Posted by master5001
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.
[/edit]

More extensive than this?
Code:

```#include <stdio.h> #define UPPER 100000 int main(void) {     int i, arr[UPPER];     unsigned long j;     for (i = 2; i < UPPER; i++) {         arr[i] = 1;     }     for (i = 2; i < UPPER; i++) {         if (arr[i]) {             for (j = i; i * j < UPPER; j++) {                 arr[i * j] = 0;             }         }     }     for (i = 2; i < UPPER; i++) {         if (arr[i]) {             printf("%d \n", i);         }     }     return 0; }```
~/
• 09-17-2004
Dave Evans
Quote:

Originally Posted by Daveo
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.

Thanks in advance to anyone that could help rectify this problem.

Using this algorithm (an application of Fermat's Little Theorom) to check whether a number, n, is prime, you have to calculate 2 to the power n.

Now, 2 to the power 10000 has a value of something like 10 to the power 3011. To represent this number in the computer requires 10000 bits. If your C-compiler uses 32-bit integers, you can't use this algorithm (with built-in C data types and operators) directly for testing numbers upto 10000. I don't think it's too much of a stretch to say that it is unlikely that any C compiler will handle 10000-bit numbers with built-in data types and operators.

Bottom line: The interesting mathematical theorem has little practical application in real computers. You could obtain packages/libraries that allow decimal arithmetic with numbers of arbitrarily large precision, but why would you do this? Other posts have mentioned practical methods.

Bottom line: it is sometimes helpful to think about what's really happening in an algorithm before trying to implement it.

Regards,

Dave

p.s. If you wrote an unsigned int power-of-2 function and checked to see if (2 to the power n-1) % n == 1, you could get all the way to n = 31 before it stopped giving answers, but that's the limit for 32-bit ints.
• 09-17-2004
laserlight
Come to think about it, it isnt a good way to start listing primes either, since it will list composite numbers along with the primes.
• 09-17-2004
Dave Evans
Quote:

Originally Posted by laserlight
Come to think about it, it isnt a good way to start listing primes either, since it will list composite numbers along with the primes.

No, it won't. The algorithm is correct, as far as it goes.

Regards,
Dave
• 09-17-2004
laserlight
Quote:

No, it won't. The algorithm is correct, as far as it goes.
Remember, Fermat's Little Theorem says nothing about composite numbers, only about primes.
At least one composite number, p, exists for which n**(p-1) mod p = 1, n != kp, where k, n and p are integers.
• 09-17-2004
Dave Evans
Quote:

Originally Posted by laserlight
Remember, Fermat's Little Theorem says nothing about composite numbers, only about primes.
At least one composite number, p, exists for which n**(p-1) mod p = 1, n != kp, where k, n and p are integers.

I stand corrected. Actually, I think I'll sit for a while. Thanks.

Dave
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12