-----------------------------------

ds_matrix

Sat Dec 15, 2007 7:06 pm


Sorting Prime Numbers

-----------------------------------

Hi, 

I just had an exam where I had to use a boolean query to calculate and list the first 10 prime numbers (1 and above)

I honestly had no idea how to do this and was wondering if anyone could tell me how?
 
Thanks


-----------------------------------

Tony

Sat Dec 15, 2007 7:18 pm


Re: Sorting Prime Numbers

-----------------------------------

list the first 10 prime numbers (1 and above)
it's a trick question, 1 is not a prime :wink:


-----------------------------------

ds_matrix

Sat Dec 15, 2007 8:37 pm


Re: Sorting Prime Numbers

-----------------------------------

list the first 10 prime numbers (1 and above)
it's a trick question, 1 is not a prime :wink:

sorry meant to say starting from 2


-----------------------------------

Tony

Sat Dec 15, 2007 8:48 pm


RE:Sorting Prime Numbers

-----------------------------------

can you post the actual question? your wording is ambigious.


-----------------------------------

PaulButler

Sat Dec 15, 2007 9:12 pm


RE:Sorting Prime Numbers

-----------------------------------

There are a few simple ways to find prime numbers. The most obvious way is to pick a number and check if any number between 1 and that number are factors of that number. If they are, the number isn't prime. You can make this more efficient by only testing for factors up to the square root of the number and only using odd numbers (making an exception to check for 2).

The second method is called the Sieve of Eratosthenes. It's a bit better when you are looking for multiple prime numbers, especially if they are low primes. If you want to find prime numbers up to n, you make a bit array of n elements all set to false. Then start with 2 and set every second bit except 2 to true. Then set every third bit except 3 to true. Then skip 4, because the fourth element of the array is true. Keep setting every xth element after x, if the xth element is false. If my explanation is bad, try wikipedias: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes .


-----------------------------------

Nick

Sat Dec 15, 2007 9:26 pm


RE:Sorting Prime Numbers

-----------------------------------

so you want just the first ten upto number n?
if so then wouldn't this be the same for every number past 29? the first 10 are:
2
3
5
7
11
13
17
19
23
29


-----------------------------------

CodeMonkey2000

Sat Dec 15, 2007 9:40 pm


RE:Sorting Prime Numbers

-----------------------------------

momop, I'm pretty sure that's not what he/she wanted.


-----------------------------------

Tony

Sat Dec 15, 2007 9:51 pm


RE:Sorting Prime Numbers

-----------------------------------

a boolean query is just an if statement... you could totally check if any given number is in this hard-coded list.

or, since we know that every number above 1 is either a prime, or has a prime factor, we could be fancy and check if one of the hard-coded values is a factor or not. Which is actually kind of how Sieve of Eratosthenes works.