Here's a function to find if a number is prime.
```java
boolean isPrime(int num) {
boolean isPrime = true;
for (int i = 2; i < num; i++) {
if (num % i == 0) {
isPrime = false;
}
}
return isPrime;
}
```
The above code is inefficient. To find if 97 is prime (and it is) we have to loop through 95 times. To find if n is prime, we have to go through the for loop roughly n times. We say the code has time complexity O(n).
We need a way to make the code more efficient.
* Firstly, the fact we're using a for loop means we always have to check all the values, even if the number turns out not to be prime on the first test (because it divides by 2). This would be better done with a while loop.
* Next, we don't need to count up to n. In fact, because a x b = b x a, you should see that we only have to count as far as n/2. This halves the range we have to check.
* Thinking about it further we see that we only need to count as far as the square root of n (because root n * root n = n)
* If a number is even it won't prime (unless it's two) so we only have to count up in odd numbers. This halves our range again. We are now only counting through a quarter of the numbers we started with.
You can reduce this further by iterating in 6s checking only n+1 and n+5 (1,5,7,11,13,17 etc). See if you can figure out why.
# Task One
Create a framework for the isPrime code (hint: see [[Solving Section B Questions]])
Make your code more efficient by applying the above.
Test your code as follows
```java
isPrime(2)
isPrime(3)
isPrime(4)
isPrime(9)
isPrime(11)
```
# Task Two
Read up on the [Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and [Memoization](https://en.wikipedia.org/wiki/Memoization). Implement these in Java