Python primary test

Question

I am trying to run a simple conformance test in Python.

Alignment with Wikipedia, the criterion of primitiveness is as follows:

Given the input number n, check to see if any integer m divides from 2 to n - 1. If n is divisible by any m, then n is compound, otherwise it is simple.

I started by striking out even numbers - with the exception of 2 - as candidates for simple

def prime_candidates(x): odd = range(1, x, 2) odd.insert(0, 2) odd.remove(1) return odd 

Then we write a function for checking primes in accordance with the above rules.

 def isprime(x): for i in range(2, x-1): if x % i == 0: return False else: return True 

And this is the main function that iterates through a list of 8000 main candidates and checks their primacy

 def main(): end = 8000 candidates = prime_candidates(end) for i in candidates: if isprime(i) and i < end: print 'prime found ' + str(i) 

The problem is that the isprime function returns True for numbers that are not prime.

Answer 1

In short, your isprime(x) checks if the number is odd coming out right after if x % 2 == 0 .

Try a small change so that you actually iterate:

 def isprime(x): for i in range(2, x-1): if x % i == 0: return False else: return True 

Note that else: now part of the for loop, not if .

Answer 2

Look at the Miller-Rabin primitive test if a probabilistic algorithm is enough. You can also prove that the number must be prime, such as Elliptic Curvature Authentication (ECPP) , but it takes more effort.

A simple trial division algorithm is

 def prime(a): return not (a < 2 or any(a % x == 0 for x in range(2, int(a ** 0.5) + 1))) 

Edit: Here is a more educational version, because the first solution is very concise and maybe harder to read:

 from math import sqrt def prime(a): if a < 2: return False for x in range(2, int(sqrt(a)) + 1): if a % x == 0: return False return True 

Instead of a ** 0.5 I replaced in sqrt(a) to make things clearer. The square root is used to not look at more factors than we need.

Answer 3

Your function really returns whether your number is odd.

In fact, what you do, you check whether 2 divides your number and returns immediately. You never check other numbers.

What you need to do is return this true value from the if else clause and the for loop to the body of the main function.

In the sidebar, If you are looking for primes below a given number, you can save the primes found in your memory, and then try just dividing your new number by these primes! (since if d is composite and divides q, then p exists such that p is prime and p divides q).

Answer 4

The problem is that you put return False in the else clause, and not at the end of the function. Thus, your function will return immediately after checking the first divisor, and not for checking other divisors.

Here is a simple primitive test similar to yours:

 def is_prime(n): d = 2 while d * d <= n: if n % d == 0: return False d += 1 return n > 1