18159: 个位为 1 的质数个数(Sieve of Eratosthenes)

sieve, http://cs101.openjudge.cn/practice/18159/

当输入一个整数 n(2<=n<=10001),要求输出所有从 1 到这个整数之间(不包括 1 和这个整数)且个位数是 1 的素数, 如果没有则输出NULL

输入

第一行是一个整数T，1 < T <10001, 表示有T个数据需要测试。 接下来的T行每行有一个大于1的正整数n。 注意时间复杂度，提示不要对每一个测试数据都从头开始找一遍素数。

输出

注意参照样例，Cases等字符也要输出。 然后输出所有从 1 到这个整数n之间(不包括 1 和这个整数) 且个位为 1 的素数(素数之 间用空格隔开,每一行输出的最后面都没有空格), 如果没有则输出NULL。

样例输入

3
5
12
110

样例输出

Case1:
NULL
Case2:
11
Case3:
11 31 41 61 71 101

来源

cs101-2017 期末机考备选

为了优化时间复杂度，我们使用埃拉托色尼筛法 (Sieve of Eratosthenes) 预先生成所有可能的素数，并在每次测试时快速筛选出符合条件的素数。

import sys

def sieve_of_eratosthenes(limit):
    """使用埃拉托色尼筛法生成从 2 到 limit 的所有素数"""
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False  # 0 和 1 不是素数
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, limit + 1, i):
                is_prime[j] = False
    return is_prime

def find_primes_with_last_digit_one(is_prime, n):
    """找出从 1 到 n-1 之间，个位数是 1 的素数"""
    primes_with_one = []
    for num in range(2, n):
        if is_prime[num] and num % 10 == 1:
            primes_with_one.append(num)
    return primes_with_one

def main():
    input_data = sys.stdin.read().strip().split('\n')
    T = int(input_data[0])  # 测试数据组数
    test_cases = list(map(int, input_data[1:]))  # 每组测试数据
    
    # 找到最大的 n，以便一次性生成所有素数
    max_n = max(test_cases)
    
    # 使用埃拉托色尼筛法生成素数表
    is_prime = sieve_of_eratosthenes(max_n)
    
    # 处理每个测试用例
    for idx, n in enumerate(test_cases, start=1):
        primes = find_primes_with_last_digit_one(is_prime, n)
        print(f"Case{idx}:")
        if primes:
            print(" ".join(map(str, primes)))
        else:
            print("NULL")

if __name__ == "__main__":
    main()

def sieve(n):
    isprime = [True]*(n+1)
    isprime[1] = False
    for i in range(2,int(n**0.5)+1):
        if isprime[i]==True:
            for j in range(2*i, n+1, i):
                isprime[j]=False
    return [str(x) for x in range(2,n) if isprime[x]]

T=int(input())
prime_l = sieve(10010)
for i in range(T):
    n = int(input())
    tmp_l = [x for x in prime_l if int(x)<n]
    primes = [x for x in tmp_l if x[-1]=='1']
    print('Case' + str(i+1) + ':')
    if primes==[]:
        print('NULL')
    else:
        print(' '.join(primes))

思路：不演了

import bisect
Lis = [11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381,1451,1471,1481,1511,1531,1571,1601,1621,1721,1741,1801,1811,1831,1861,1871,1901,1931,1951,2011,2081,2111,2131,2141,2161,2221,2251,2281,2311,2341,2351,2371,2381,2411,2441,2521,2531,2551,2591,2621,2671,2711,2731,2741,2791,2801,2851,2861,2971,3001,3011,3041,3061,3121,3181,3191,3221,3251,3271,3301,3331,3361,3371,3391,3461,3491,3511,3541,3571,3581,3631,3671,3691,3701,3761,3821,3851,3881,3911,3931,4001,4021,4051,4091,4111,4201,4211,4231,4241,4261,4271,4391,4421,4441,4451,4481,4561,4591,4621,4651,4691,4721,4751,4801,4831,4861,4871,4931,4951,5011,5021,5051,5081,5101,5171,5231,5261,5281,5351,5381,5431,5441,5471,5501,5521,5531,5581,5591,5641,5651,5701,5711,5741,5791,5801,5821,5851,5861,5881,5981,6011,6091,6101,6121,6131,6151,6211,6221,6271,6301,6311,6361,6421,6451,6481,6491,6521,6551,6571,6581,6661,6691,6701,6761,6781,6791,6841,6871,6911,6961,6971,6991,7001,7121,7151,7211,7321,7331,7351,7411,7451,7481,7541,7561,7591,7621,7681,7691,7741,7841,7901,7951,8011,8081,8101,8111,8161,8171,8191,8221,8231,8291,8311,8431,8461,8501,8521,8581,8641,8681,8731,8741,8761,8821,8831,8861,8941,8951,8971,9001,9011,9041,9091,9151,9161,9181,9221,9241,9281,9311,9341,9371,9391,9421,9431,9461,9491,9511,9521,9551,9601,9631,9661,9721,9781,9791,9811,9851,9871,9901,9931,9941]
t = int(input())
for _ in range(1, t + 1):
    print(f"Case{_}:")

    n = int(input())
    cut = bisect.bisect_left(Lis, n)
    if cut:
        print(" ".join(list(map(str, Lis[:cut]))))
    else:
        print("NULL")