22 Mar 07
i'm doing a project for my honours course where i essentially have to code something-anything-in maple. so i thought it would be nice to look at prime sieves and compare them to maple's in built isprime() function (which uses fermats little theorem). so far i've got a fully functioning sieve of Eratosthenes', and am working on a sieve of Atkin. does anyone know of any other fancy ways of either creating lists of or generating prime numbers?
thanks 🙂
22 Mar 07
1 edit
Originally posted by geniusif you like C language or c++ I think it's quite easy to make a routine that checks if a given number is a prime or not. then all you have to is to store the ones that your routine says are primes.
i'm doing a project for my honours course where i essentially have to code something-anything-in maple. so i thought it would be nice to look at prime sieves and compare them to maple's in built isprime() function (which uses fermats little theorem). so far i've got a fully functioning sieve of Eratosthenes', and am working on a sieve of Atkin. does anyone kn ...[text shortened]... f any other fancy ways of either creating lists of or generating prime numbers?
thanks 🙂
22 Mar 07
Originally posted by geniusA good reference is The Lore of Prime Numbers by G. P. Loweke (1982). The bibliography there leads to more specific references in special areas that you are mentioning.
i'm doing a project for my honours course where i essentially have to code something-anything-in maple. so i thought it would be nice to look at prime sieves and compare them to maple's in built isprime() function (which uses fermats little theorem). so far i've got a fully functioning sieve of Eratosthenes', and am working on a sieve of Atkin. does anyone kn ...[text shortened]... f any other fancy ways of either creating lists of or generating prime numbers?
thanks 🙂
22 Mar 07
Originally posted by adam warlockNot quite what genius is looking for. The C routine is likely using a brute force method (there is no easy way to check if a given number is prime for a large given number leaving aside deterministic tests for the moment).
if you like C language or c++ I think it's quise to make a routine that checks if a given number is a prime or not. then all you have to is to store the ones that your routine says are primes.
Other possibly interesting prime checks could be:
Wilson's Theorem (If (x - 1)! = -1(mod x) then x is prime or 4, if it is not then x is composite)
Proth's Theorem http://mathworld.wolfram.com/ProthsTheorem.html (Finds primes of a certain form)
Or if you want a challenge, the Pollard rho Factorization Method. A fast factorization method that involves iteration until some form of stable behaviour is reached.
22 Mar 07
Originally posted by XanthosNZI was just about to write that as I saw your post arrive...........damned!
Not quite what genius is looking for. The C routine is likely using a brute force method (there is no easy way to check if a given number is prime for a large given number leaving aside deterministic tests for the moment).
Other possibly interesting prime checks could be:
Wilson's Theorem (If (x - 1)! = -1(mod x) then x is prime or 4, if it is not th ...[text shortened]... t factorization method that involves iteration until some form of stable behaviour is reached.
22 Mar 07
Originally posted by XanthosNZthe C routine is brute force indeed, but i thought it could be fun for him to do it and the routine is quite easy to do. and afterwards he could refinite a little bit. but the best way is to use sharper methods.
Not quite what genius is looking for. The C routine is likely using a brute force method (there is no easy way to check if a given number is prime for a large given number leaving aside deterministic tests for the moment).
Other possibly interesting prime checks could be:
Wilson's Theorem (If (x - 1)! = -1(mod x) then x is prime or 4, if it is not th ...[text shortened]... t factorization method that involves iteration until some form of stable behaviour is reached.
22 Mar 07
Originally posted by adam warlockthe "sharper methods" is what he's asking about...
the C routine is brute force indeed, but i thought it could be fun for him to do it and the routine is quite easy to do. and afterwards he could refinite a little bit. but the best way is to use sharper methods.
23 Mar 07
Originally posted by XanthosNZyeah. i know that. the c routine that i was thinking about does exactly that too. at least in the way i'm thinking that he should implement it. that was one of the first things i learned in college so i don't think it'll be to hard for him to do.and with it he might get a feel of what the sharper methods are about.
The sieve of Eratosthenes' is a brute force method of finding primes, except it gives you all the primes up to a number.
but i don't understand why you replied that to me... 😕
23 Mar 07
Originally posted by adam warlockwell, the harder it is to code the better, really...the more complicated my project the better my chances are of getting a good grade... 😛
yeah. i know that. the c routine that i was thinking about does exactly that too. at least in the way i'm thinking that he should implement it. that was one of the first things i learned in college so i don't think it'll be to hard for him to do.and with it he might get a feel of what the sharper methods are about.
but i don't understand why you replied that to me... 😕