Problem 2: Finding Primes

Go down

Problem 2: Finding Primes

Post  Elusive on Sat Jun 04, 2011 3:43 pm

What is a prime number, specified by order?

Inputs: Which prime number to return, e.g. 1st, 8th, etc. Will be supplied as an integer.
Outputs: Prime number, specified by input.


1st prime num: 2

50th prime num: 229

10000th prime num: 104729

  1. Wikipedia wrote:A prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself.
    Therefore, 1 is not a prime number, and 2 is the first prime number.
  2. Don't use an online prime generator, that won't help you learn to code one.
  3. You can use an online prime checker to make sure the numbers your program returns are prime.
  4. Arrays in C based languages are zero-indexed (start at 0), while the number specified will be indexed at one (starts at 1). Remember that if you are using one.
  5. Numbers above one million could take some time to find, so it is best to perform tests with smaller numbers.
  6. This can be solved recursively or in a loop, I personally used a loop for simplicity.
  7. If trial division (dividing by every number below it) is too slow, here are a few ways to speed it up:
    1. Spoiler:
      It is not necessary to check multiples of 2
    2. Spoiler:
      You only need to divide by numbers below the square root of the number you are checking.
    3. Spoiler:
      Prime sieves are much faster.


Posts : 10
Join date : 2011-06-04

View user profile

Back to top Go down

Back to top

- Similar topics

Permissions in this forum:
You cannot reply to topics in this forum