Stuck on how to store the highest prime number

[Sizz]

Hey all,

Basically, I am suppose to compute 10 numbers and find their highest prime number for each of them.

I've already have the inputs working, and set up 2 arrays to store inputs and their highest prime number. But I am uncertain on how to find and store their highest prime number. Can anyone give me an idea how to start it off?

Thanks.

[Adak]

Welcome to the forum, Sizz!

How large are these numbers - can you hold them in an int array?

Do you have a run-time requirement (maybe 5 or 10 seconds) or no time limit? Trial by division method is easy, but slow. Sieve of Eratosthenes is much faster, and not much harder at all. If the numbers aren't too large, the Sieve of E. would be perfect for this job.

Read up on the Sieve of Eratosthenes on Wikipedia, and see what you think.

[Sizz]

Hey Adak,
No, I don't have a runtime requirement. I think my main problem is, if i input 10 numbers, I need to find all the prime numbers from each input i make. Is there an efficient way of doing this??

Oh and thanks for the suggestion on wikipedia, its quite good .

[iMalc]

So by "compute" do you mean to "factorise"?
If that's not correct then you'll need to explain yourself better.

[grumpy]

Regardless of what "compute" means, the method of storing a prime value depends on the magnitude of that prime value. I certainly have no idea what "compute highest prime for a value" means, and won't even speculate.

Virtually all C compilers support a long unsigned type, which is able to represent any integral value between zero and 4294967295. Most modern compilers support a long long unsigned type, which is guaranteed able to represent any integral value between zero and 18446744073709551615. If you need a larger prime value than that, or you have an older compiler that does not support long long types, then you need to find an alternative approach.

[Sizz]

Ahhhhhhh sorry for the confusion. I meant "input" instead of "compute".

[Adak]

Hey Adak,
No, I don't have a runtime requirement. I think my main problem is, if i input 10 numbers, I need to find all the prime numbers from each input i make. Is there an efficient way of doing this??

Oh and thanks for the suggestion on wikipedia, its quite good .

OK, so your program will be taking input for 10 numbers, and needs to find the largest prime number less than each of those 10 numbers, is that right?

So if the first number is 18, you need the prime number 17 as the answer?

If so, I'd put the 10 input number into a small array, and sort them, in ascending order (small...big). Now you're set to use the Sieve of Eratosthenes, because it finds ALL the prime numbers as it works - and every time it passes the value of inputNumbers[i], you have your answer for the next input number at primeNumber[i-1].

//inside the Sieve of E.:



if(primeNumber[i] > inputNumber[j]) {
     printf("Next answer is: %d \n",primeNumber[i-1]);
     increment j; //inputNumber[] index
}
increment i; //primeNumber[] index

The primeNumber[] array is the primeNumbers you have found as the Sieve of E, works. You could do this loop and if() statement either inside the Sieve, or just have the Sieve work until it finds all the primes less than the highest number, and then use the above logic inside a second loop, outside the Sieve.

[iMalc]

Ahhhhhhh sorry for the confusion. I meant "input" instead of "compute".

This still leaves us guessing about the rest of it. We aren't mind readers. Lets not play 20 questions with this one.