Primality testing. More...

Functions
def	isPrime (n)
	Tests whether an integer is prime. More...

def	isPrime2 (n)
	Using list comprehensions creates a list with all divisors of 'n'. More...

def	main (argv=None)

Variables
	xrange = range

Detailed Description

Primality testing.

A prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself.

Only divisors up to $\lfloor \sqrt{n} \rfloor$ (where $\lfloor x \rfloor$is the floor function) need to be tested. This is true since if all integers less than this had been tried, then $\frac{n}{(\lfloor\sqrt{n}\rfloor+1)} < \sqrt{n}.$ In other words, all possible factors have had their cofactors already tested. Given a factor a of a number n=ab, the cofactor of a is b=n/a.

Trial division, used here, is hopeless for finding any but small prime numbers. Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test combined with a Lucas pseudoprime test.

See also: https://literateprograms.org/miller-rabin_primality_test__python_.html

Assuming that $2^{61}-1$ is prime (2305843009213693951), the algorithm will do about $2^{60}$ divisions (if not using the $\lfloor\sqrt{n}\rfloor$ limit). Supposing that the computer can perform $10^{9}$ divisions per sec (1 gigaflop), then this will take approximately 36 years: $\frac{1152921504606846976}{(1000000000*31536000)}=36.558901085$

Using the $\lfloor\sqrt{n}\rfloor$ limit, this falls to $\frac{1518500249}{2*1000000000} = 0.759s$
On a Quadcore Q6600 (64 bits), this python program took 100s.
The same program written in C took 17s. Therefore, the C program is almost 6 times faster.
On a Pentium 4, 2.60GHz (32 bits), this python program took 1295.3035109 s (21.5 min).
On a Eightcore i7-2600 CPU @ 3.40GHz (64 bits), this python program took 45s.
The same program written in C took 6.5s.

There are several prizes for those who discover large prime numbers, such as a $250,000 to the first individual or group who discovers a prime number with at least 1,000,000,000 decimal digits.

Author: Paulo Roma

Since: 28/12/2008

See also: http://primes.utm.edu/howmany.shtml; http://en.wikipedia.org/wiki/FLOPS; http://www.intel.com/support/processors/sb/CS-023143.htm#1; http://www.easycalculation.com/prime-number-chart.php; http://www.eff.org/awards/coop

Function Documentation

◆ isPrime()

def _04a_prime.isPrime ( n )

Tests whether an integer is prime.

Parameters

n	given integer.

Returns: 0 if n is prime, or one of its factors, otherwise.

References _04b_intsqrt.intsqrt(), and xrange.

Referenced by main().

◆ isPrime2()

def _04a_prime.isPrime2 ( n )

Using list comprehensions creates a list with all divisors of 'n'.

If the list is empty, then 'n' is prime (very inefficient). Ex. n = 100 -> return not [2, 4, 5, 10]

See also: http://www.secnetix.de/olli/Python/list_comprehensions.hawk

◆ main()

def _04a_prime.main ( argv = None )

References _01d_dec2bin.input, and isPrime().

Variable Documentation

◆ xrange

_04a_prime.xrange = range

Referenced by isPrime().

Functions