What's problematic about finding out if a large number is Prime or not? 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.
 A: Probably what you have read (in the context of public key encryption) is that it is hard to factor a large integer in its prime divisors if each of these divisors is large. In essence, factoring a number consisting of $n$ bits into prime components, requires trial divisions using numbers containing up to $\frac12n$ bits. As there are $2^{n/2}$ such numbers, this computational effort scales exponentially. More specifically, every two additional bits in the number to be factored, doubles the computational effort.  
One can improve upon this scaling by using more advanced algorithms, but there is no known algorithm that one could run on present-day computers that would make the computational effort scaling as a polynomial in the number of bits. 
Checking for a number being prime or composite (rather than explicitly finding the composites) can actually been done in polynomial time. In highly optimized algorithms the computational effort scales with the sixth power of the number of bits ($n^6$).
A: It sounds like you've got the gist. You actually only need to check up to $\sqrt{N}$. The reason for this is that if $N$ is divisible by $a$, with $a\geq \sqrt{N}$, then $N=ab$, where $b\leq\sqrt{N}$. So if you check up to $a$, you would have checked $b$ already. And even then there are better and faster methods that mathematicians have come up with. But however you do it, you have to make a lot of calculations.
And I mean a lot of calculations. big numbers here are numbers with hundreds of digits. Even if you only check up to $\sqrt{N}$, that is still over $10^{50}$ calculations, one hundred trillion trillion trillion trillion. Doing these calculations can be done quickly, but to do so many of them takes a while.
A: 
What I am missing in terms of it being hard to compute?

Let $k$ denote the length of your input.
If your input number is $N$, then $k\approx\log_2N$, and therefore $N\approx2^k$.
The runtime complexity of an algorithm is measured as a function of the input-length.
Since the runtime complexity of your algorithm is $O(N)$, it is also $O(2^k)$, hence exponential.
A: 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).
A: I would like to choose somewhat different perspective than in the other answers and say something about the topic in question. For me, it is hard to determine whether some (big enough) number is prime because prime numbers tend to exhibit strange enough behavior which still is not understood. See for example this conjecture. If this conjecture is correct then, in a certain sense, its correctness reveals why it is hard to determine when we will stumble upon a prime in the sequence of natural numbers because sometimes from the prime $p$ to the next prime $q$ we will have only to add $2$ to $p$ to obtain $q$, sometimes $4$, sometimes $80$, sometimes $222$, just choose even numbers which you like at the moment, any should do the work, should it?
Another reason, closely related to the above written thoughts, is that it is not easy to determine whether (big enough) number is prime because we do not have (correct me if we have) general enough and efficient enough methods that would settle whether some number is prime or not. To clarify this suppose that we investigate sequence $a_n=\sum_{i=0}^n 10^i$. This is just the sequence of numbers such that $n$-th term has $n+1$ ones in the base $10$ representation. Even for this sequence (which is simple to describe) we still do not have necessary and sufficient condition for primality of the terms in the sequence, so you can imagine how hard could it be to find the theorem of the form "$n$ is prime if and only if "this hols"" which is such that gives testing for primality in a straightforward easy-to-calculate way.
