C Practice Example 33 - Prime Number Determination
Title:Determine whether a number is prime.
Program analysis:Prime numbers, also called primes, are infinite in number. A natural number greater than 1 that cannot be divided by any other natural number except 1 and itself.
Program source code:
Example
#include<stdio.h>
#include<math.h>
#define MAX 1000 // Maximum array size
int prime[MAX]; // Array to store whether it is a prime number
// Simple method to determine if a number is prime (brute force)
int isPrimeNaive(int n)
{
if (n <= 1) // Numbers less than or equal to 1 are not prime
return 0;
for (int i = 2; i < n; i++) // Check from 2 to n-1 one by one whether they divide n
if (n % i == 0) // If it divides evenly, then it is not prime
return 0;
return 1; // If no factor is found, then it is prime
}
// Optimized prime check: only check up to sqrt(n) and skip even numbers
int isPrime(int n)
{
if (n <= 1) // Numbers less than or equal to 1 are not prime
return 0;
if (n == 2) // 2 is prime
return 1;
if (n % 2 == 0) // Exclude even numbers
return 0;
int limit = (int)sqrt((double)n); // Only need to check up to sqrt(n)
for (int i = 3; i <= limit; i += 2) // Start from 3 and only check odd numbers
{
if (n % i == 0) // If it divides evenly, then it is not prime
return 0;
}
return 1; // Passed all tests, n is prime
}
// Sieve initialization: create prime table
void sieve()
{
for (int i = 0; i < MAX; i++)
prime[i] = 1; // Assume all numbers are prime
prime[0] = prime[1] = 0; // 0 and 1 are not prime
int limit = (int)sqrt((double)MAX); // Only need to check up to sqrt(MAX)
for (int i = 2; i <= limit; i++) // Start from 2 and loop through every number
{
if (prime[i]) // If i is prime
{
for (int j = i * i; j < MAX; j += i) // Mark multiples of i as non-prime
prime[j] = 0;
}
}
}
// Determine whether a number is prime using the sieve method
int isPrimeSieve(int n)
{
return prime[n]; // Directly return whether that index is prime
}
int main()
{
sieve(); // Initialize prime sieve
// Test various numbers to see if they are prime
printf("N=%d %d\n", 1, isPrime(1)); // Output: 1 is not prime
printf("N=%d %d\n", 2, isPrime(2)); // Output: 2 is prime
printf("N=%d %d\n", 3, isPrime(3)); // Output: 3 is prime
printf("N=%d %d\n", 4, isPrime(4)); // Output: 4 is not prime
printf("N=%d %d\n", 7, isPrime(7)); // Output: 7 is prime
printf("N=%d %d\n", 9, isPrime(9)); // Output: 9 is not prime
printf("N=%d %d\n", 13, isPrime(13)); // Output: 13 is prime
printf("N=%d %d\n", 17, isPrime(17)); // Output: 17 is prime
printf("N=%d %d\n", 100, isPrime(100)); // Output: 100 is not prime
printf("N=%d %d\n", 23, isPrime(23)); // Output: 23 is a prime number
printf("N=%d %d\n", 1, isPrime(1)); // Output: 1 is not prime
return 0;
}
The output result of the above example is (a trailing digit of 1 indicates a prime number, 0 indicates not a prime number):
N=1 0 N=2 1 N=3 1 N=4 0 N=7 1 N=9 0 N=13 1 N=17 1 N=100 0 N=23 1 N=1 0other extensions