[ad_1]
Asked
Viewed
43 times
I wrote this function to check if a number ‘n’ is a prime:
int isPrime(const long long int n) {
long long int d = 3; /* Division by 0 has no meaning.
Any number is perfectly divisible by 1.
And any even number greather then 2 is not a prime
number (we'll perform a separate check for 2).
So we shall start the division at 3. */
if (n <= 1)
return 0; // 0 and 1 are not prime numbers.
if (n == 2)
return 1; // 2 is the only even prime number.
if (n % 2 == 0)
return 0; /* If 'n' is an even number other than 2 (see above), by
definition it can not be a prime number. */
while ((d * d) < (n / 2)) /* Looking for an integer proper divisor of 'n' (with 'n' is an
odd number) smaller than sqrt(a/2). */
{
if (n % d == 0)
return 0; // Looking for a proper divisor other then 1.
d += 2; // We skeep even numbers.
}
return 1; /* If there does not exist a proper divisor other then 1, by
definition 'n' is prime number. */
}
I wonder if anyone knows a more efficient way to accomplish this task.
asked 1 hour ago
16
If your requirement is bigger numbers and repeatitive, I suggest using sieve algorithm, which creates an array of booleans. For every index if the number is prime, the value will be true otherwise false.
checkout this tutorial for more: https://youtu.be/7zYMjXqdchc
answered 50 mins ago
Not the answer you’re looking for? Browse other questions tagged c math or ask your own question.
lang-c
[ad_2]