[Algorithm/C] Project Euler. 10001st prime
10001st_prime.cClick to download.
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
If a good upper bound for the target prime is known in advance, using a sieve of Eratosthenes is a much more efficient method.
Some useful facts:
1 is not a prime.
All primes except 2 are odd.
All primes greater than 3 can be written in the form 
Any number n can have only one primefactor greater than 
The consequence for primality testing1 of a number n is : if we cannot find a number f less than or equal
#include <stdio.h>
#include <math.h>
int isPrime(int n)
{
if(n==1)
{
return 0;
}
else if(n<4)
{
return 1;
}
else if(n%2==0)
{
return 0;
}
else if(n<9)
{
return 1;
}
else if(n%3==0)
{
return 0;
}
else
{
double r = floor(sqrt((double)n));
int f = 5;
while (f<=r)
{
if(n%f==0)
{
return 0;
}
else if(n%(f+2)==0)
{
return 0;
}
f += 6;
}
return 1;
}
}
int main(int argc, char * argv[])
{
int limit = 10001;
int count = 1;
int candidate = 1;
while(1)
{
candidate += 2;
if(isPrime(candidate))
{
count++;
}
if(count==limit) break;
}
printf("%d",candidate);
}
문제 출처 - https://projecteuler.net/problem=7
- A primality test is an algorithm for determining whether an input number is prime. primality tests do not generally give prime factors, only stating whether the input number is prime or not. [본문으로]