## liliy 2 years ago Write a method that determines whether a given number is prime. Note that you run a loop i/2

1. srossd

Well, you could do this a lot of different ways. One way is to check every number under n to see if it divides n. Here's the code for that (in Java first, and then Python, tell me if you want it in a different language): public boolean isPrime(int n) { for(int i = 2; i < n; i++) { if(n % i == 0) return false; } return true; } def isPrime(n): for i in range(2,n): if(n % i == 0): return False return True I'll post an explanation of a more efficient way to do this next.

2. srossd

A few mathematical observations can vastly improve the running time of this method. The first of those observations is that we don't need to check every number 2 through n-1; we only need to check up to the square root of n. Write out the factors for some composite numbers to convince yourself of that; it's impossible to have factors above sqrt(n) without having some below it too. Here's another observation: think about taking all the values of i in mod 6. Things that are 0, 2, 3, or 4 mod 6 are composite, since they're divisible by either 2 or 3 (the exception to that rule being, of course, 2 and 3 themselves). So, given those two pieces of information, here's java and python code to check primality much much faster than the other code: public boolean isPrime(int n) { if(n % 2 == 0 || n % 3 == 0) return false; int i = 5; while(i <= Math.sqrt(n)) { if(n % i == 0) return false; if(i % 6 == 5) i += 2; else i += 4; } return true; } def isPrime(n): if n % 2 == 0 or n % 3 == 0: return False i = 5 while i < math.sqrt(n): if n % i == 0: return False if i % 6 == 5: i += 2 else: i += 4 return True There you go, tell me if you have more questions.

3. liliy

but my teacher said use the i/2 method , wat is that?

4. slotema

One way to use approximately i/2 iterations is by simply excluding all even numbers (except for two), since they are a multiple of two. Therefore, you would only need to check if the number is a multiple of 2 and the odd numbers (3, 5, 7, 9, 11, etc.)