01.求200万以内的质数

一、题目思路

1、设两个整数a和b，如果不是质数的话，整数x就可以写成 x=a * b 比如：

36 = 2 * 18
36 = 4 * 9 
36 = 6 * 6

        如果整数x为质数，就不可能写成x = a * b的形式，即如果不为质数，其中一个可整除的因数一定满足小于等于根号x，缩短遍历判断范围，即判断到根号x是否能整除即可

2、质数定义：大于1的自然数，且除了1和它本身外没有其他正因数。故大于2的奇数才可能是质数，偶数除了2以外不可能是质数

二、代码实现

#include <stdio.h>
#include <math.h>
 
int main() {
    int i = 0, flag = 0, j = 0, count = 0;
    for (i = 3; i <= 2000000; i += 2) 
    {
        flag = 1;
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                flag = 0;
                break;
            }
        }
        if (1 == flag)
        {
            printf("%d ", i);
            count++;
        }
    }
    printf("\ncount = %d", count);
    
    return 0;
}

1、2可以直接输出，代码中没有写出

2、i为外层循环，遍历2000000内的数（从3开始，每次+2，因为大于2的奇数才可能是质数）

3、j为内层循环，判断i的是否有整除的因数，判断范围到根号i即可（sprt(i)）