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)

*/*Define the maximum number */

#include "stdio.h"

#define N 200 /

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 */

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);/

}

}

return 0;

}