Problem 2: Finding Primes
Problem 2: Finding Primes
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.
Example:
Tips:
Inputs: Which prime number to return, e.g. 1st, 8th, etc. Will be supplied as an integer.
Outputs: Prime number, specified by input.
Example:
- Code:
1st prime num: 2
- Code:
50th prime num: 229
- Code:
10000th prime num: 104729
Tips:
Therefore, 1 is not a prime number, and 2 is the first prime number.Wikipedia wrote:A prime number (or a prime) is a natural number that has exactly two distinct natural number divisors: 1 and itself.- Don't use an online prime generator, that won't help you learn to code one.
- You can use an online prime checker to make sure the numbers your program returns are prime.
- 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.
- Numbers above one million could take some time to find, so it is best to perform tests with smaller numbers.
- This can be solved recursively or in a loop, I personally used a loop for simplicity.
- If trial division (dividing by every number below it) is too slow, here are a few ways to speed it up:
- Spoiler:
- It is not necessary to check multiples of 2
- Spoiler:
- You only need to divide by numbers below the square root of the number you are checking.
- Spoiler:
- Prime sieves are much faster.
Elusive- Newbie
- Posts : 10
Join date : 2011-06-04
Permissions in this forum:
You cannot reply to topics in this forum
|
|