0

I wrote a program which is not important now, but it was on this Fermat's theorem. Now the problem is the output was not as expected. I know the question is not too good or off the mark but I just can't solve the error which is that there is an occurrence of 4 here in the output which must not be there. I'm unable to debug it.

The theorem: This Image 

for x in range(1,100):
 m=5**(x-1)
 if m%x>1:    
   pass
 else:
   print"prime",x

Output is this:

This is output

S.L. Barth is on codidact.com
  • 8,198
  • 71
  • 51
  • 66
TreaV
  • 23
  • 8
  • *output was not as expected*, What was the expected output? Additionally. Please don't post images as code, [See this meta post](https://meta.stackoverflow.com/q/285551/3933332). Also see [ask] and what is a [mcve] – Bhargav Rao Dec 25 '16 at 06:57
  • @bhargav-rao the output would not include 4 (see image attached )but it has since the theorem isn't wrong so there must be error somewhere – TreaV Dec 25 '16 at 06:59
  • Kindly [edit] your post and add the description of your error there. – Bhargav Rao Dec 25 '16 at 07:00
  • @Bhargav Rao Added – TreaV Dec 25 '16 at 07:04
  • Add it _as text_. – TigerhawkT3 Dec 25 '16 at 07:11
  • 3
    also note that a `p` which passes the test is not necessarily prime; all the theorem states is that a `p` which does not pass the test is not prime. – hiro protagonist Dec 25 '16 at 08:21
  • `print "prime",x` is a mathematical miunderstanding. FLT provides a sufficient test for compositeness, not a sufficient test for primality (although it does provide a necessary test for primality). – John Coleman Dec 25 '16 at 15:07

1 Answers1

1

A perfect explanation is found here: https://stackoverflow.com/a/29596459/5110035

Basically this method is not very accurate. I found a pattern in your code. If a is chosen 5, then a-1 non-prime is printed. That's why 4 comes up. Change it to 7 and you get 6. But also other errors come up such as 25.

Fermat's Little Theorem can be easily written in Python like this:

def CheckIfProbablyPrime(x): return pow(2, x-1, x) == 1

The only reason why I think four comes up is because of your algorithm being a bit incorrect. Sieve of Eratosthenes, once it finds a non-prime it then gets rid of its multiples such as 4 is a multiple of 2 but 2 is prime as 4 is not. It checks less numbers and much faster. Look into that.

Community
  • 1
  • 1
MichaelMMeskhi
  • 659
  • 8
  • 26
  • 1
    In `CheckIfProbablyPrime` better test multiple small primes, for example randomly pick the four primes 2,5,11,23, this should catch most of the false positives up to mediums sized numbers. Perform test with prime `p` only if `x>p`. – Lutz Lehmann Dec 25 '16 at 09:37