求素数

[编程题]求素数

热度指数：3307 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

两个整数M，N

输出描述:

区间内素数的个数

示例1

输入

2 10

输出

算法知识视频讲解

Python

华科平凡

python解法

使用埃拉托斯特尼筛法

基本思想：素数的倍数一定不是素数
实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
如果n*n > 范围最大值就跳出。

import math


def count_prime(N):
    n = int(math.sqrt(N) + 1)
    arr = [True] * (N + 1)
    for i in range(2, n):
        for j in range(2, N):
            if i * j <= N:
                arr[i * j] = False
            else:
                break
    return sum(arr) - 2


start, end = map(int, input().split())
print(count_prime(end) - count_prime(start - 1))

要注意start要减去1。

发表于 2019-02-24 19:30:05 回复(1)