After writing a program in C language to determine the odd or even nature of an integer yesterday, I suddenly thought: since we can determine odd or even, can we also use C language to determine if an integer is a prime number?
A prime number, also known as a prime, is an integer that can only be divided by 1 and itself, such as 2, 3, 5, 7, 11, 13, 17, 19, etc. In today’s computer science community, known prime numbers have reached over 41 million, a scale that is astronomical.
These giant primes have no direct application in reality, but they symbolize the highest honor in the challenges of mathematics, software, and hardware, representing a kind of soft power competition and display.
After six years, humanity discovered a new largest prime, which has 16 million more digits—the discoverer donated the prize to educational institutions.
Although ordinary people with home PCs cannot participate in such competitions, writing a small C program to determine whether a number is a prime is completely feasible.
First, we need to determine the method for judging prime numbers:
Method 1: Brute Force Enumeration
According to the definition of a prime number, the expression for a prime number N is 1xN. To determine if an integer N is prime, we can check all integers from 2 to N-1 to see if they can divide N; if any can divide it, then N is not a prime number.
This method directly utilizes the definition and is easy to understand, but it has a clear flaw: when N is large, the computational load increases rapidly for both the human brain and the computer, leading to inefficiency.
Method 2: Square Root Optimization
According to the properties of factors, if N is a composite number (not a prime number), then N can be expressed as a·b, where either a or b must be less than or equal to √N (the square root of N). Therefore, we only need to check if integers in the range [2, √N] can divide N; if no integers can divide it, then N is a prime number.
In simple terms, if a number N can be factored into two factors a and b, then one of these factors must be less than or equal to √N, and the other must be greater than or equal to √N. If the two factors are equal, then that factor is √N.
For example, consider the case of composite numbers:
Taking 100 as an example, its integer factor combinations are:2×50,4×25,5×20,10×10, we can see that 2, 4, 5 are all less than 10, which is the square root of 100, while 10 is exactly equal to the square root of 100.
If both factors are less than the square root of 100, for example, 9 × 9 = 81 < 100;
If both factors are greater than the square root of 100, for example, 11 × 11 = 121 > 100
Similarly, for the composite number 10000, one of its two integer factors must be less than or equal to 100:
If both factors are less than 100, for example, 99 × 99 = 9801 < 10000
If both factors are greater than 100, for example, 101 × 101 = 10201 > 10000
This illustrates a rule: for any composite number N, at least one of its two integer factors is not greater than √N (the square root of N).
The core of the square root optimization method is that if no factors that can divide the number are found among the integers less than or equal to the square root, then this number is not composite, and it can be determined that it is a prime number.
We will demonstrate with smaller primes:
1. Determine if 29 is a prime number:
Using Method 1, the brute force enumeration method: we need to check 2~28, which requires checking 28 numbers.
You might argue:“When I tried 29 ÷ 2, 29 ÷ 3, 29 ÷ 4, 29 ÷ 5, I found none can divide it, so I wouldn’t continue checking. Because 29 divided by any integer greater than 5 will yield a quotient less than 5, and all integers less than 5 cannot divide 29, so there is no need for extra calculations.”
That’s right, this reflects the flexibility of the human brain in quickly adjusting strategies during thought.
However, if a computer follows Method 1, it will check each number in the order set by the program until the end, unlike us humans who can skip unnecessary calculations in advance.
Method 2: Square Root Optimization:√29≈5.38, so we only need to check 2, 3, 4, 5, which requires only 4 calculations.
2. Determine if 83 is a prime number.
From the comparison of Method 1 and Method 2, we know that Method 2 is simpler. We only need to check integers less than or equal to √83, which are 2, 3, 4, 5, 6, 7, 8, 9, to see if they can divide 83; this requires only 8 calculations, rather than over 80 as in Method 1.
It is evident that when the numbers are larger, the efficiency advantage of Method 2 is very significant. For example, to determine if 10003 is a prime number: Method 1 requires tens of thousands of calculations, while Method 2 requires only about 100 calculations. As the numbers grow larger, this difference becomes even more pronounced.
Since our C language small program is more of an exercise and a game, we can try to write both methods once.
Method 1: C Program to Determine if a Number is Prime Using Brute Force Enumeration:
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <stdlib.h> // 判断是否为质数（暴力枚举法）int isPrime(int n) { if (n <= 1) return 0; // 小于等于1的数不是质数 for (int i = 2; i < n; i++) { if (n % i == 0) return 0; } return 1;} // 找到一个非平凡因子并打印表达式void printFactor(int n) { for (int i = 2; i < n; i++) { if (n % i == 0) { printf("%d = %d x %d\n", n, i, n / i); return; } }}int main() { int num; while (1) { system("cls"); // 清屏 printf("请输入一个整数 (输入0或负数退出): "); scanf("%d", &num); if (num <= 0) break; if (isPrime(num)) { printf("%d 是质数。\n", num); } else { printf("%d 不是质数，是合数。\n", num); printFactor(num); } printf("按回车继续..."); getchar(); // 吃掉换行符 getchar(); // 等待用户按回车 } printf("程序已退出。\n"); return 0;}Output:
Method 2: C Program to Determine if a Number is Prime Using Square Root Optimization:
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <math.h>#include <stdlib.h> // 判断是否为质数的函数int isPrime(int n) { if (n <= 1) return 0; // 小于等于1的数不是质数 if (n == 2) return 1; // 2是质数 if (n % 2 == 0) return 0; // 偶数（除2外）都不是质数 for (int i = 3; i <= sqrt(n); i += 2) { if (n % i == 0) return 0; } return 1;} // 找到一个非平凡因子void printFactor(int n) { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { printf("%d = %d x %d\n", n, i, n / i); return; } }}int main() { int num; while (1) { system("cls"); // 清屏 printf("请输入一个整数 (输入0或负数退出): "); scanf("%d", &num); if (num <= 0) break; if (isPrime(num)) { printf("%d 是质数。\n", num); } else { printf("%d 不是质数，是合数。\n", num); printFactor(num); } printf("按回车继续..."); getchar(); // 吃掉换行符 getchar(); // 等待用户按回车 } printf("程序已退出。\n"); return 0;}Output:
From the results, although the brute force enumeration method requires more calculations to determine if a number is prime, the square root optimization method requires fewer calculations, yet both show no significant difference in actual running speed, providing answers within the expected time.
Does this mean that the superiority of the square root optimization method does not exist? The answer can be both yes and no.
On modern computers, even ordinary home PCs can perform calculations at speeds fast enough to complete millions or even tens of millions of operations in a time frame that we humans can hardly perceive. Therefore, for small-scale integer judgments, both methods perform almost equally in terms of time.
However, when faced with extremely large values (for example, in competitions for finding the largest prime), the efficiency differences between different algorithms become apparent. In such scenarios, the advantages of the square root optimization method become clear, and competitions will also introduce more advanced optimization algorithms, specialized software, and hardware acceleration methods to enhance performance.
Undeniably, our two C language small programs are quite interesting!