First off, your code is both short and correct, which is very good for at beginner. ;-)
This is what I would do to improve the code:
1) Define the variables inside the loops, so they don't get confused with something else. I would also make the bound a parameter or a constant.
#define MAX 1000
for(int i=2;i<MAX;i++){
for(int j=2;j<i/j;j++){
if(!(i%j)) break;
if(j>(i/j)) cout<<i<<" is prime\n";
}
}
2) I would use the Sieve of Eratosthenes, as Joey Adams and Mau have suggested. Notice how I don't have to write the bound twice, so the two usages will always be identical.
#define MAX 1000
bool prime[MAX];
memset(prime, sizeof(prime), true);
for(int i=4;i<MAX;i+=2) prime[i] = false;
prime[1] = false;
cout<<2<<" is prime\n";
for(int i=3;i*i<MAX;i+=2)
if (prime[i]) {
cout<<i<<" is prime\n";
for(int j=i*i;j<MAX;j+=i)
prime[j] = false;
}
The bounds are also worth noting. i*i<MAX is a lot faster than j > i/j and you also don't need to mark any numbers < i*i, because they will already have been marked, if they are composite. The most important thing is the time complexity though.
3) If you really want to make this algorithm fast, you need to cache optimize it. The idea is to first find all the primes < sqrt(MAX) and then use them to find the rest of the
primes. Then you can use the same block of memory to find all primes from 1024-2047, say,
and then 2048-3071. This means that everything will be kept in L1-cache. I once measured a ~12 time speedup by using this optimization on the Sieve of Eratosthenes.
You can also cut the space usage in half by not storing the even numbers, which means that
you don't have to perform the calculations to begin working on a new block as often.
If you are a beginner you should probably just forget about the cache for the moment though.