#!/usr/bin/env python
# coding: UTF-8
#
## @package _04a_prime
#
# 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 @f$\lfloor \sqrt{n} \rfloor@f$ (where @f$\lfloor x \rfloor@f$is the floor function) need to be tested.
# This is true since if all integers less than this had been tried, then
# @f$\frac{n}{(\lfloor\sqrt{n}\rfloor+1)} < \sqrt{n}.@f$
# 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 https://literateprograms.org/miller-rabin_primality_test__python_.html
#
# Assuming that @f$2^{61}-1@f$ is prime (2305843009213693951),
# the algorithm will do about @f$2^{60}@f$ divisions
# (if not using the @f$\lfloor\sqrt{n}\rfloor@f$ limit).
# Supposing that the computer can perform @f$10^{9}@f$ divisions per sec
# (1 gigaflop), then this will take approximately 36 years:
# @f$\frac{1152921504606846976}{(1000000000*31536000)}=36.558901085@f$
# - Using the @f$\lfloor\sqrt{n}\rfloor@f$ limit, this falls to
# @f$\frac{1518500249}{2*1000000000} = 0.759s@f$
# - 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 http://primes.utm.edu/howmany.shtml
# @see http://en.wikipedia.org/wiki/FLOPS
# @see http://www.intel.com/support/processors/sb/CS-023143.htm#1
# @see http://www.easycalculation.com/prime-number-chart.php
# @see http://www.eff.org/awards/coop
import sys
from math import sqrt
sys.path.append("./") # path for searching modules
from _04b_intsqrt import intsqrt
try:
xrange
except NameError:
xrange = range
##
# Tests whether an integer is prime.
#
# @param n given integer.
# @return 0 if n is prime, or one of its factors, otherwise.
#
def isPrime(n):
if (n == 1):
return 1 # 1 is not prime
elif n < 4: # 2 and 3 are primes
return 0
elif n % 2 == 0:
return 2 # composite
else:
limit = intsqrt(n) # trunc to the lowest integer
for i in xrange(3, limit + 1, 2):
if n % i == 0:
return i # composite
return 0 # prime
##
# 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 http://www.secnetix.de/olli/Python/list_comprehensions.hawk
#
def isPrime2(n):
return not [x for x in range(2, int(sqrt(n)) + 1) if n % x == 0]
def main(argv=None):
if argv is None:
argv = sys.argv
if len(argv) < 2:
num = int(input("Please, enter a positive integer: "))
else:
num = int(argv[1])
import time
t0 = time.time()
res = isPrime(num)
print("Run time: %es" % (time.time() - t0))
if (res):
print("%s is Composite because it is divisible by %s" % (num, res))
else:
print("%s is Prime because it is only divisible by 1 and itself" % num)
if __name__ == "__main__":
sys.exit(main())