Prime Numbers

damnyanks

Was just looking at some questions asked in interviews for software developers. This one sorta stumped me...

Generally the questions involve you doing something rather basic such as outputting the date. However you cannot use any built in functions

Anyways... one of them was to print out prime numbers. As I said I got stuck on that one. Can anyone tell me how I'd go about doing that ? I guess my maths isn't so great

Hobbes

N is a prime if the square root of N is not divisible by any number below it (exception being 1).

However to check quicker, check to see if it is divisble by 2 or 3 and if not then check all the primes up to the square root of N.

You could probably speed it up again by building you prime table beforehand, or on previous calls to your function.

Talliesin

There are lots of different algorithms for finding primes, some very complex, and this is an area of ongoing research (generally speaking finding big primes is difficult because you have to check that every number from 2 to its square root isn't a factor).

For relatively small numbers you can find the primes in the range 1-n using the Sieve of Eratosthenes. Create an array of n booleans. Set them all to false.
Mark every second element as true (but skipping the second element)
Mark every third element as true (but skipping the third)
... and so on until you have done this for every √n element.

Now those booleans in the array that are false correspond to primes.

bonkey

Assuming the task is to find all primes less than some arbitrary limit, rather than whether or not X is a prime (for any given X), then you only need to check whether or not the number is divisible by any prime found so far (up to a max of root(toCheckifPrime), or to when (prime-previously-found^2) > toCheckifPrime (to avoid using the sqrt function if thats not allowed).

jc

Talliesin

Eh, isn't that exactly what I just said?

Capt'n Midnight

There are many speed ups.
eg: 2 is prime so you only look at odd numbers
3 is prime so you only check for primes at 6n+1 and 6n-1
- if you could find a generic formulae for this you could skip most of the numbers dead handy.

These speedups can also be used in the Sieve since you can fit more numbers in RAM if you know which to ignore.

For breaking codes that use prime numbers you no longer have to work out all the primes because there is a cheat. If you take a numbers and divide it by some primes then each time you get a remainder, the higher the probability that it's really a prime number. So rather than doing exhaustive testing you could divide your canidate numbers by say 30 primes and any that pass this quick test would then be used to attack the code. You waste time because not all the numbers you use will be true primes, but you save shed loads of time because you don't have to prove they are.

If you have to find all the prime numbers between 1 and N then you need to put the answers in columns Len(N)+1 wide, so you would need fixed width text formatting (eg: Print using ###### etc. ) the usual line feeds when you go past 80/132 and a form feed or some end of page character at the end

Talliesin

Capt'n Midnight wrote:

There are many speed ups.
eg: 2 is prime so you only look at odd numbers
3 is prime so you only check for primes at 6n+1 and 6n-1

That merely restates the solution differently. The principal is still "find a prime, block off all its multples".

Capt'n Midnight wrote:

- if you could find a generic formulae for this you could skip most of the numbers dead handy.

If you could find a truly generic formula (expressable as "look for prime at blah times n plus blah" etc) then finding primes would have constant complexity, breaking assymetric encryption would be trivial and probably hundreds of people would end up getting a bullet in the back of their heads (a mixed curse, so of them would be right bastards).

Capt'n Midnight

Just pointing out that there have been a lot of optimisations for prime searching and showing the most basic example.

The principal is "find a prime, block off [SOME of] its multples". - with the 6n you don't have to cross off for any multiple that is a product of 3 , saves about 1/3 of the time. The problem with the generic formula I've given is that the number of terms grows geometrically and it does not predict all primes and so would be no use for the purists, but it would be very useful as an ignore list to speed up cracking.

If you can't use any of the built in functions then change to one of the old text video modes and write directly to video memory