-1

The best method known to me is of order sqrt(n). I read about Fermat’s Primality Test and Miller-Rabin Primality Test. They operate in O(log(n)) time, but a major drawback is that they fail sometimes as well. Can you help me out?

If possible provide an algorithm and code in python ( Even algorithm will be sufficient).

rajah9
  • 11,645
  • 5
  • 44
  • 57
Shambhav Agrawal
  • 131
  • 7
  • 1
    Does this answer your question? [Checking if a number is a prime number in Python](https://stackoverflow.com/questions/4114167/checking-if-a-number-is-a-prime-number-in-python) or this [Fastest way of testing if a number is prime with Python](https://stackoverflow.com/questions/46841968/fastest-way-of-testing-if-a-number-is-prime-with-python) or this [Python Prime number checker](https://stackoverflow.com/questions/18833759/python-prime-number-checker) – khelwood Jul 31 '20 at 13:04
  • The failure rate isn't typically something to worry about in practice. The odds of a false positive from Miller-Rabin after *k* rounds is 1 in 4^(-k). Even for a small value of `k`, like 20, there is a significant difference between sqrt(n) and k*log(n) for the large values of `n` where you need something faster than naive divisor testing, and Miller-Rabin, in that case, will report a composite number as such 99.9999999999% of the time. – chepner Jul 31 '20 at 13:16
  • And the 4^(-k) is a *conservative* estimate; for large `n` the rate drops to 8^(-k) or even lower. – chepner Jul 31 '20 at 13:23

1 Answers1

-1

Here's what I found after a quick search in google. Tested and seems to work. The check for if the number is higher than 1 can be changed to num > 0 if you consider 1 a prime number.

# Program to check if a number is prime or not

num = 407
    
# prime numbers are greater than 1
if num > 1:
   # check for factors
   for i in range(2,num):
       if (num % i) == 0:
           print(num,"is not a prime number")
           print(i,"times",num//i,"is",num)
           break
   else:
       print(num,"is a prime number")
       
# if input number is less than
# or equal to 1, it is not prime
else:
   print(num,"is not a prime number")

Credit: https://www.programiz.com/python-programming/examples/prime-number

Ivailo Hristov
  • 25
  • 1
  • 6