Skip to content

11242: 【原1242】Prime Number

题目

题目描述

author: Lin Li 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1242

Description

某助教的表妹是一个小萝莉，笑响点亮了四面风，轻灵在春的光艳中交舞着变。小萝莉今天刚刚在课上学了素数，很是高兴，她跑去问助教表哥，她想知道任意两个给定整数之间有多少个素数。

Input Format

一行，两个空格隔开的整数A，B。1 <= A <= B <= 10000

Output Format

一个整数，表示A和B之间所有素数的个数。

Sample Input

2 6

Sample Output

3

yyong119's solution 

#include <cstdio>
#include <cmath>
#include <cstring>
#define MAX_N 10010
using namespace std;
int a, b, ans;
bool pr[MAX_N];
int main() {
    scanf("%d%d", &a, &b);
    pr[1] = true;
    for (register int i = 2; i <= sqrt(b); ++i)
        if (!pr[i])
            for (register int j = 2; i * j <= b; ++j) pr[i * j] = true;
    for(register int i = a; i <= b; ++i)
        if (!pr[i]) ++ans;
    printf("%d\n", ans);
    return 0;
}