Originally Posted by
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
.
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].
Code:
//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.