#!/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())