primality test function is_prime (n, k) based on Fermat Little Theorem,

401 Views Asked by At

I solved this question: Implement a primality test function is_prime (n, k) based on Fermat Little Theorem, where n is the number to be tested, and k is the number of bases to be used. The function should return False if n is not prime, and True if n is pseudoprime to these k bases. Notice that k is a small constant, and therefore, some composites will be counted as primes.

def is_prime (n, k) :
    bases = []
    for i in range(2,k+1):
        bases.append(i)
    for base in bases:
       a =  math.pow(base,n-1) % n
       if (a==1):
           return True
           
       else:
           False

testing for primes under 20000, for k = 10

bases = int(input("Enter the number of bases: "))

for m in range(1,2000):

    print(is_prime(m,bases))
    print(m)

this the error:

 File "/Users/IA/Desktop/ICS254_Project/project.py", line 48, in <module>
    print(is_prime(m,bases))
  File "/Users/IA/Desktop/ICS254_Project/project.py", line 30, in is_prime
    a =  math.pow(base,n-1) % n
OverflowError: math range error

What is wrong and how can I correct it?

0

There are 0 best solutions below