Thread: Huge Array Problem

  1. #16
    The larch
    Join Date
    May 2006
    Posts
    3,573
    In my defence:
    I found the first 25,000 primes, not 250,000 primes.

    Also, I can't see how it would find pseudo-primes. It is based on the theorem which says that each number which is not a prime, can be factored into primes. Ergo: if a number is divisible by some number (= any non-prime), it is also divisible by some primes.

    I looked up pseudo-primes in Wikipedia and that is something completely different. For example, they say that the first pseudo-prime is 341 = 11*31. Pseudo-primes can also be found with this method, because they can be divided by some primes.

    (Ok, found 250,000 primes in 73 seconds on 256 MB RAM. And I knew exactly how much memory to set aside )
    Last edited by anon; 01-18-2007 at 10:50 AM.

  2. #17
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    Quote Originally Posted by vart
    Seems to be explicit conversion of the array index to the int type
    Man that sounds greek and latin to me, I know C programming but aint a pro at your levels, a more elaborate explanation would be highly appreciated.

  3. #18
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your values for array sizes are just too large in the first case, and in the second, the compiler see's that humongous number as being negative, because it's WAY WAY WAY, too large.

    I would like to know, like Dave Sinkula, why you don't want to put this data into a file?

    Having all these primes in a single array all at once is 1) Impossible because there are just too many apparently for your system or compiler, and 2) awkward to view or do anything productive with the data just sitting there in a very large array.

    If you want more answers or comments to your program, you'll have to first indent it. What's in your first post is bound to cause errors - way beyond any excuse I can think of. If you can code, you can learn a decent coding style, very easily.

    Adak
    Last edited by Adak; 01-18-2007 at 11:37 AM.

  4. #19
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    Indented Code:
    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    void main()
    {
        long unsigned int limit=4294967294;
        long unsigned int n,i,flag,j=1;
        clrscr();
        for (n=2; n<limit; n++) 
        {
            flag=1;
            if (n==2) 
    	{
                printf("2");
                continue;
            } 
    	else 
    	{
                if (n%2==0) 
    	    {
                    continue;
                }
            }
            for (i=3; i<=sqrt(n)+1; i+=2) 
    	{
               if (n%i==0) 
    	   {
                    flag=0;
                    break;
               }
            }
            if (flag==1) 
    	{
                j++;
                printf("%luth prime is %lu\n",j,n);
            }
        }
        getch();
    }
    As for your question adak, i dont know file handling at all, so i will need some very specific pointers to it. I know it sounds lame, but havent yet learnt it.

  5. #20
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    1. int main
    2. print 2 before loop
    3. start loop with 3 and make step +=2 as in the second loop

    to understand the implicit (my fault) conversion try
    int limit=4294967294;
    and print this value as %d
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  6. #21
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Oh!

    Sorry to be so ticked off, then.

    I believe the obvious question is
    "What do you want to do with these prime numbers once your program has found them?"

    Do you want to print them in columns on paper? Put them in a file for later reference, or what?

    And Vart is quite right with his suggestions. In C, the main() function should always return an int, (unlike C++), so it's ALWAYS :

    int main(AnyParametersNeeded)
    and
    return = 0; indicates normal program completion.

    All other functions may be void or return a value, that's all up to you.

    Moving the if (n == 2) ... is also good. No need for the program to be testing this thousands of times, when it will only be true once. It should go before the main loop begins.

    Your program looks not only much better, but far less apt to cause errors in either execution, or understanding.

    We can help you print these numbers to a file - no problem.

    Adak

  7. #22
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    Thanks for the concern.
    It aint about the list of the numbers that is whether i print them or keep them in a file is no concern. I am just trying to push my programming capability limits to edge. I wanted to write a program which can find really huge primes and also make it fast.

    I am learning C programming and instead of trying lame ass assignment/homework questions I prefer taxing my brain on such things.

  8. #23
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Might surprise you to learn that writing a program which finds the prime numbers is a classic student's assignment and classroom exercise.

    One thing you should investigate is just what your system's upper (and lower) limits are for char's, int's, unsigned and unsigned, long's (signed and unsigned), and float.

    A little while loop which will test the incremented value to see if it's greater than one will be needed, and it needs to print out the highest value. (You may want to just subtract a 1 from it after it goes negative to find that highest value.)

    I'd be sure to write those numbers and their data type, down for future reference. This is a constant concern for a programmer.

    Adak

  9. #24
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by torqu3e
    It aint about the list of the numbers that is whether i print them or keep them in a file is no concern. I am just trying to push my programming capability limits to edge. I wanted to write a program which can find really huge primes and also make it fast.

    I am learning C programming and instead of trying lame ass assignment/homework questions I prefer taxing my brain on such things.
    Then perhaps do some research into various algorithms.
    http://en.wikipedia.org/wiki/Primality_test

    Basic hacks to a brute-force algorithm will not produce any meaningful results towards your aim.

    And learning files might be a smarter approach so you can break this problem down into manageable steps -- or else have the ability to leave your program run for very long periods of time. (I took your original and modified it little, basically making it write to separate files of a given size -- I started it last night and it's now up to the 361st file of 250000 primes, and this was the last one of file #360: 1834925069.)

    Quote Originally Posted by torqu3e
    As for your question adak, i dont know file handling at all, so i will need some very specific pointers to it. I know it sounds lame, but havent yet learnt it.
    There's not that much to it. Declare a FILE, fopen a file, change printf to fprintf, fclose the file when done.

    An extremely basic start that you must admit you know you can handle -- and which I had already mentioned -- is to pipe the output to a file. That would be done by replacing your invocation (assuming Windows) from this:
    H:\Forum\C\myapp.exe
    to this:
    H:\Forum\C\myapp.exe > output.txt
    For me, with minor tweaks to your original, it ran at the command prompt in about 63 seconds and the piped version ran in 2.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  10. #25
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    You might want the good ol' Sieve
    en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    Or the spankin' new one
    en.wikipedia.org/wiki/Sieve_of_Atkin
    Which is by the way already written out nicely for you
    cr.yp.to/primegen.html
    primegen is a small, fast library to generate prime numbers in order. It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  11. #26
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    Code:
    [root@Torqu3e Desktop]# more primes.C 
    #include<stdio.h>
    #include<math.h>
    //#include<conio.h>
    int main(void)
    {
        long unsigned int limit=4294967294;
        long unsigned int n,i,flag,j=1;
        //clrscr();
    printf("2");
            for (n=2; n<limit; n++)
        {
            flag=1;
    
               for (i=3; i<=sqrt(n)+1; i+=2)
            {
               if (n%i==0)
               {
                    flag=0;
                    break;
               }
            }
            if (flag==1)
            {
                j++;
                printf("%luth prime is %lu\n",j,n);
            }
        }
        //while(!kbhit());
       //return(0);
    }
    [root@Torqu3e Desktop]# gcc primes.C -m32
    primes.C:6: warning: this decimal constant is unsigned only in ISO C90
    /tmp/ccU1sLtb.o: In function `main':
    primes.C:(.text+0xa8): undefined reference to `sqrt'
    /tmp/ccU1sLtb.o:(.eh_frame+0x11): undefined reference to `__gxx_personality_v0'
    collect2: ld returned 1 exit status
    Any insights into this error?

  12. #27
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,974
    > [root@Torqu3e Desktop]
    Set up a normal account, and stop writing code and surfing the net as root. One misplaced command or the wrong website, and you're looking for your re-installation disks.

    > long unsigned int limit=4294967294;
    Add the suffix LU to the end, say
    long unsigned int limit=4294967294lu;

    > for (i=3; i<=sqrt(n)+1; i+=2)
    If you want real performance (well better anyway), do the sqrt() once rather than on every iteration of the loop

    > primes.C:(.text+0xa8): undefined reference to `sqrt'
    The math library is -lm not -m32

    > undefined reference to `__gxx_personality_v0'
    .C means C++ code, yet you're using a C compiler.
    Either rename the file to be primes.c
    or compile it with g++ primes.C
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. simple array of char array problem
    By cloudy in forum C++ Programming
    Replies: 5
    Last Post: 09-10-2006, 12:04 PM
  2. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  3. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  4. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM
  5. From stream/file to a string array problem
    By dradsws in forum C Programming
    Replies: 2
    Last Post: 10-01-2001, 06:24 PM