banner
李大仁博客

李大仁博客

天地虽大,但有一念向善,心存良知,虽凡夫俗子,皆可为圣贤。

[Algorithm] Implement two algorithms for finding prime numbers (brute force method, sieve method) in the C programming language.

I can't remember the questions from today's exam. I will analyze them for you once they are made public. Today, let's talk about some classic algorithms - finding prime numbers. I believe many people still remember the brute force method, which continuously divides each number by all numbers smaller than its square root until a result is obtained. The time complexity of this algorithm is O(N^2). The optimized algorithm has a time complexity of O(N * sqrt(N)). I won't go into detail about the classic algorithm. If beginners don't understand it, they can leave a comment or contact me.

Here is the code:

/* Classic method for finding prime numbers - brute force

  • author CG
  • 2008 12 21
  • Time complexity: O(N * sqrt(N))
    */
    #include "stdio.h"
    #include "math.h"

#define N 200 /* Define test data /
int main() {
int i , j;
for(i = 2 ; i <= N ; i++) {
for(j = 2 ; j <= (int)sqrt(i) ; j++){/
Compare until j reaches sqrt(i) */
if(i % j == 0){
break;
}/if/
}/for/

if(j > (int)sqrt(i)){/* Does it meet the condition? /
printf("%-10d",i);/
Output */
}/if/
}/for/
return 0;
}/main/

The following is currently one of the most commonly used methods for finding prime numbers. Of course, there are more superior algorithms that utilize Fermat's Little Theorem to achieve a probability distribution of prime numbers and implement an algorithm with nearly linear time complexity. I won't discuss it today. Interested? Then keep following me. If I have time recently, I will post the code.

Alright, today's protagonist: Sieve of Eratosthenes for finding prime numbers. The principle is to filter the desired prime numbers from the existing array data. It requires an N-sized space, where N is the range of the prime numbers being sought. Compared to the classic algorithm, it is more wasteful but more efficient, with a time complexity of O(N * LogN). It is suitable for finding prime numbers in a large range, but space waste is also objective.

Principle: Starting from index j=2,0,1, exclude these cases and then start filtering all multiples of j, and then filter j+1 until j=N, completing the filtering.

Here is the specific algorithm:

/* Sieve of Eratosthenes for finding prime numbers

  • author CG
  • 2008 12 21
  • Time complexity: O(N * LogN)
    /
    #include "stdio.h"
    #define N 200 /
    Define the maximum number */

int main() {
double s , t;
int num[ N + 1 ] = {0};
int j = 2 ;/* Define the starting number, starting from 2 /
int i ;/
Counter /
for(i=2 ; i<=N ; i++) {
num[i] = 1;
}
while(j <= N) {
if(num[j] == 1) {
for(i = j + j ; i <= N ; i += j) {
num[i] = 0;
}
}
j++;
}
for(i = 2 ; i <= N ; i++) {
if(num[i] == 1) {
printf("%-10d", i);/
Output */
}
}
return 0;
}

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.