[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)

[ttw]

One can cast out small numbers (perhaps by "wheels" rather than trial division; wheels do several divisions at once) then switch to SQUFOF or Pollard's Rho or Pollard's P-1 method.

However, I digress as I only read part of an answer. The above is for factoring. Prime testing is also interesting. There is a polynomial-time algorithm but it runs in m^6 power or so where m is the length of the candidate.

There are several good tests. The Selfridge-Pomerance-Wagstaff test is rather nice (I'll try it later this year sometime). The Wiki has good article on prime testing.