mecrazycoder,
Yes, determining if a number is prime can be done in polynomial time. If you want to know all the prime numbers up to a certain value, the best way is probably the sieve of Eratosthenes (or a variation). There are also websites that list all prime numbers up to certain values that you could just create a lookup table for such a small number (1 million isn't very big). Given how limited your post is, it is hard to tell what you really want. Math::Pari has functions for determining primeness.