Very simple question

[Lej1]

I am trying to write a program that stores all the prime numbers up to 1000 in an array.. I can do that.. but when it's doing the check to see if it's prime, if it isn't, it just sets it to 0. So when I try to print out all my prime numbers, it prints all the 0s out with it. How do I remove the 0s from the array? Or what's a better way to do this..

[rags_to_riches]

Don't print it if the value in the array is 0? Alternatively, don't store it in the array if the it's not prime?

[Lej1]

The first suggestion works, however, how would I not store it in the array? (with continuing the check)


Here's your first suggestion:

    for(i = 0; i < size; i++)
    {
	if (arr[i]!=0)
		printf("%d ",arr[i]);
    }

Works great!.. what would be more efficient though?

[javaeyes]

The sieve of Eratosthenes is considered the correct design pattern for finding prime numbers up to n. Wiki it.

[Lej1]

Yes javaeyes.. the code I wrote is doing just that. But they still have to be stored regardless..

[quzah]

No. The Sieve only stores primes, and then uses the list of primes to check new numbers to see if they are primes.


Quzah.

[Lej1]

Only "stores" the primes? .. So let's look at it like this. I am going to write a program to find all the primes up to 6. (1 will be considered prime.)

So, I make an empty array with how many spots to store primes?

[javaeyes]

Oh, nice. I was on a kick with c and prime numbers for a long time. I was trying to find a function to produces them, or at least a function that accepts a prime and returns a prime. You can burn ALOT of time trying to find such a function. And it probably doesn't even exist, now that is abstract and thankless hacking. Why are you doing this?

[javaeyes]

I though you only had to check up to the sqrt of the n not all the way, for TSOFE, BUT ur code is gone. I forget what you had. cheers.

[grumpy]

(1 will be considered prime.)

Why? 1 is not prime.

So, I make an empty array with how many spots to store primes?

There are 168 primes less than 1000.

[laserlight]

If you want to store the "prime numbers up to 1000", then certainly you only need an array with as many elements as there are "prime numbers up to 1000": these elements will be the prime numbers themselves. But if you want to use the sieve of Eratosthenes to find the "prime numbers up to 1000", then you need an array of about 1000 elements: these elements will be boolean flags that represent whether the corresponding number has been determined to be composite. Those elements that have not been determined to be composite after the algorithm is done are prime.

No. The Sieve only stores primes, and then uses the list of primes to check new numbers to see if they are primes.

That sounds more like brute force primality testing with prime numbers.

I though you only had to check up to the sqrt of the n not all the way, for TSOFE

That sounds more like brute force primality testing.

[javaeyes]

I'm rereading the sieve, you only need to check up to i/2, as the sieve begins with 2. It's odd to think that there in no mathematical function to determine whether a number is prime, nor a function to produce primes. Only algorithms. That's my 5:30 AM thought of the morning.

[grumpy]

I'm rereading the sieve, you only need to check up to i/2, as the sieve begins with 2.

Actually, it is only necessary to check to the square root of i, and the reason has nothing to do with "sieve begins with 2".

Think about it. If x has a factor that exceeds the square root of x then it also has a factor that is less than square root of x.

However, it is a good idea to avoid using sqrt() from <math.h> to compute the square root of an integer. There are algorithms for finding the integer square root.

It's odd to think that there in no mathematical function to determine whether a number is prime, nor a function to produce primes. Only algorithms. That's my 5:30 AM thought of the morning.

All mathematical functions execute algorithms. The implementation of that algorithm may be either in code or invoked by specialised machine instructions.

There are lots of problems with various choices of algorithm (each choice having different computational trade-offs) and for which the best choice of algorithm depends on needs of the program. Testing primality is one of those. So is generating primes.

Which basically means that, if you want a function to test for primality, you need to write a function that executes some appropriate algorithm.

[javaeyes]

Ok, whomever can write code that can count the number of primes up to a googol and execute in the shortest amount of time wins the Javaeyes optimized sieve of Eratosthenes to a googol Prize. The JOSOETAGP. Under one minute the prize is a coffee mug. Under one second, the mug is full of beer.

[grumpy]

It's easy to get an approximation on the count. For large n (although it is debatable whether a googol is big enough to quality as "large") it was shown mathematically in the 19th century that the number of primes less than or equal to n approaches n/log(n). That means the number of primes less than a googol is approximately 10^98.

The Sieve of Eratosthenes is reasonably efficient for small primes (say up to a few million or maybe even a billion). Good luck using it to count or find primes up to a googol under a minute on any real-world computer (with a finite processor speed and finite memory).