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?
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.
More extensive than this?Originally Posted by master5001
~/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; }
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.
Last edited by Dave Evans; 09-17-2004 at 10:07 AM.
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.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
No, it won't. The algorithm is correct, as far as it goes.
Regards,
Dave
Remember, Fermat's Little Theorem says nothing about composite numbers, only about primes.No, it won't. The algorithm is correct, as far as it goes.
At least one composite number, p, exists for which n**(p-1) mod p = 1, n != kp, where k, n and p are integers.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
I stand corrected. Actually, I think I'll sit for a while. Thanks.
Dave
