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; my algorithm is fine. I checked my primes and they are all prime. I forot about that temp pointer for ...

  1. #16
    Registered User linuxdude's Avatar
    Join Date
    Mar 2003
    Location
    Louisiana
    Posts
    926
    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?

  2. #17
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  3. #18
    ... kermit's Avatar
    Join Date
    Jan 2003
    Posts
    1,528
    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;
    }
    ~/

  4. #19
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    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.
    Last edited by Dave Evans; 09-17-2004 at 10:07 AM.

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,594
    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.
    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

  6. #21
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    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

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,594
    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.
    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

  8. #23
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    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

Page 2 of 2 FirstFirst 12
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