试除法求素数

目录

一、题目

描述

输入描述：

输出描述：

示例1

二、结论

三、代码

四、讲解

五、注意点：

---

一、题目

描述

输入M、N，1 < M < N < 1000000，求区间[M,N]内的所有素数的个数。素数定义：除了1以外，只能被1和自己整除的自然数称为素数

输入描述：

两个整数M，N

输出描述：

区间内素数的个数

示例1

输入：

2 10

复制输出：

4

二、结论

若n为素数，则 2~sqrt（n）之间所有数字一定不会被n整除。

三、代码

#include <math.h>
#include <stdio.h>
 
int main() {
   
    int a = 0, b = 0;
 
    scanf("%d %d", &a, &b);
    getchar();
 
    int count = 0;
    
    for (int i = a; i <= b; i++)
    {
        int k = 0;
 
        int flag = 0;   
 
        for (k = 2; k <= (int)sqrt(i) ;k++)
        {
            if(i % k == 0)      //如果能整除，说明不是素数
            {
                flag = 1;
                break;
            }
 
        }
 
        if (flag == 0)
            count++;
 
    }
 
    printf("%d\n", count);
 
    return 0;
}

四、讲解

 for (int i = a; i <= b; i++)
    {
        int k = 0;
 
        int flag = 0;   
 
        for (k = 2; k <= (int)sqrt(i) ;k++)
        {
            if(i % k == 0)      //如果能整除，说明不是素数
            {
                flag = 1;
                break;
            }
 
        }
 
        if (flag == 0)
            count++;
 
    }

1.默认为素数，

当flag == 1，则不为素数。

2.

double sqrt (double x);

最好将数据类型强制转化为 int

3.为了追求时间复杂度，没必要将 2~n所有数据都试除，只需要将 2~sqrt（n）的所有数据试除就好。

五、注意点：

flag需要封装在循环内部