題目描述

小明剛剛學習了素數的概念：如果一個大于?1?的正整數，除了?1?和它自身外，不能被其他正整數整除，則這個正整數是素數。現在，小明想找到兩個正整數?A?和?B?之間（包括?A?和?B）有多少個素數。

輸入格式

輸入只有一行兩個正整數?A,B。約定?2≤A≤B≤1000。

輸出格式

輸出一行，包含一個整數?C，表示找到?C?個素數。

輸入輸出樣例

輸入 #1

2 10

輸出 #1

4

輸入 #2

98 100

輸出 #2

0

說明/提示

【樣例解釋 1】

在?2?和?10?之間有?4?個素數，分別為：2、3、5、7。

思路分析

這道題的重點就在如何判斷一個數是不是質數。

方法1

枚舉所有可能為?x?因數的數??2≤a≤x?1，

如果?xmoda=0，

那么?x?就是合數；

反之，

x?就是質數。

可以得出，

這樣的時間復雜度是?O(n)，

對于本題來說已經足夠了，

但是還有更快的方法嗎？

方法2

容易發現，x=a×b，其中?a≤x?,b≥x?，那么如果?xmoda=0，那么我們無需再去查詢?xmodb?是否為?0。根據這個思路，我們無需枚舉?2～x?1，只需枚舉?2～x??即可。這樣的時間復雜度是?O(n?)?的。

---

但是對于可能?x<2?的情況，那么?x?就一定不是質數了。

代碼實現

#include <bits/stdc++.h>
using namespace std;
int ss(int n){ // 根據方法2判斷是否為質數if(n<2)return false;for(int i=2;i<=sqrt(n);i++){if(n%i==0)return false;}return true;
}int main() {int t,a;;cin>>t>>a;int n=0;for(int i=t;i<=a;i++){if(ss(i))n++;}cout<<n;return 0;
}

給個贊吧