I was reading somewhere that it's hard to determine if a number is prime or not if it gets too large.
If I understand correctly, all numbers can be broken into prime factors. And numbers which can't be broken down to any factors beside $1$ and themselves are prime.
So to check if $N$ is prime, you need to
calculate prime numbers upto $N/2$, (as any number bigger than $N/2$ can't be a factor for $N$ since multiplying it with the minimum number that will have effect, which is $2$, will make it more than $N$).
and check if any of these are factors of $N$.
I want to know if I am right, and what I am missing in terms of it being hard to compute.
Best Answer
The most brute force procedure that is not inefficient for completely naive reasons is trial division up to $\lfloor \sqrt{n} \rfloor$, because if $n$ has a factor greater than or equal to $\sqrt{n}$ then it must also have a factor less than or equal to $\sqrt{n}$. (For example, $\lfloor \sqrt{91} \rfloor = 9$. Although $91$ has a factor of $13$ which is larger than $9$, it also has a factor of $7$, and dividing by this factor reveals the factor of $13$.)
The difficulty is that if $n$ has 100 digits then $\sqrt{n}$ is like $10^{50}$, so if you try a trillion numbers per second then it will take you more than $10^{30}$ years to finish trying all the factors less than $\sqrt{n}$.
There are much better algorithms out there, though, especially for the problem of primality testing (as opposed to factorization of a number which is known to be composite).