I can't remember the questions for today's exam. I will analyze them for everyone 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, and then obtains the result. The time complexity of this algorithm is O(N^2), and 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)){/*Meets the condition?*/
printf("%-10d",i);/*Output*/
}/*if*/
}/*for*/
return 0;
}/*main*/
The following is currently the most commonly used method for finding prime numbers. Of course, there are more superior algorithms that utilize Fermat's Little Theorem to achieve an algorithm complexity close to linear. I won't discuss it today. Are you interested? Then continue to follow 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 a space of size N, 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 wastage is also objective.
Principle: Starting from index j=2,0,1, exclude these cases, then start filtering all multiples of j, and then filter j+1 until j=N, and the filtering is complete.
The specific algorithm is as follows:
/*Sieve of Eratosthenes for finding prime numbers
*author CG
*2008 12 21
*Algorithm 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; /*Initialize all numbers as potential prime numbers*/
}
while(j<=N) {
if(num[ j ] == 1) {
for(i=2*j ; i<=N ; i+=j) {
num[ i ] = 0; /*Filter out multiples of j*/
}
}
j++;
}
for(i=2 ; i<=N ; i++) {
if(num[ i ] == 1) {
printf("%-10d",i); /*Output*/
}
}
return 0;
}