Huge Array Problem

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 )

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.

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

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.

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

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

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.

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

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

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.

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:

[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?

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