So I'm making a program where I input a number, and it determines whether that number is prime or not. The method determining whether it is prime or not is determining if it is divisible by 2, it knows it is not prime. If it isn't, it tests if it is divisible by 3… and so on until it tests if it is divisible by X-1 which if it isn't, it then concludes that the number is prime. The problem with this method is that it is extremely slow. I soon realized that I could save time by setting N as half of X or 1/3 or 1/4 or 1/5… of x because, throughout the process, we would have tested 1-5…, and since it can only be divided by whole numbers, if N is set to anything higher than 1/5… of X, the second factor that multiplies with N to make X, can only go down to other numbers that the program already tested for.
So my problem is this: I want to optimize my program so that it tests the least amount of possible factors before determining whether X is prime. I need to minimize N so that knowing that X is not divisible by 2 through N, we can determe that X is prime.
Best Answer
If $X$ is not prime, then it has a prime divisor less than or equal to its square root. To check if $X$ is prime, try to divide by all primes up to $\sqrt{X}$. There's no need to check for division by $4$ or $6$ or any other composite number, because if say $6$ divides the number, so does $2$ and $3$ and you've already checked those.