蓝桥杯|蓝桥杯素数（二）蓝桥杯|算法|排序算法|算法

文章目录

P1125 [NOIP2008 提高组] 笨小猴
- 分析
- 代码
- - 通过截图
质数
- 分析
- 代码（一个很普通的方法）
- - 通过截图
- 代码（埃筛法）
- - 通过截图

P1125 [NOIP2008 提高组] 笨小猴 【蓝桥杯|蓝桥杯素数（二）】

文章图片

分析

这个我直接用Counter计数器做方便快捷。利用Counter计数器进行统计，统计完直接遍历字典的值即可。最大值和最小值肯定会大于等于1，所以最小值初值设成0，由于字符串长度小于100，所以最大值初值设为100。

代码

import math from collections import Counter def is_prime(n): if n == 1 or n == 0: return False m = int(math.sqrt(n)+1)for i in range(2,m): if n % i == 0: return False return Trues = input() s_dic = Counter(s) Max = 0 Min = 100 for i in s_dic.values(): if i > Max: Max = i if i < Min: Min = iif is_prime(Max-Min): print("Lucky Word") print(Max-Min) else: print("No Answer") print(0)

通过截图

文章图片

质数

题目描述给定一个正整数 N，请你输出 N 以内（不包含 N）的质数以及质数的个数。输入描述输入一行，包含一个正整数 N。 1≤N≤1000 输出描述共两行。第 1 行包含若干个素数，每两个素数之间用一个空格隔开，素数从小到大输出。第 2 行包含一个整数，表示N以内质数的个数。输入输出样例示例输入10输出2 3 5 7 4运行限制最大运行时间：1s 最大运行内存: 128M

分析

第一种方法就不说了就是简单的遍历到根号n查询
第二种方法比较有意思叫埃筛法，比如我有一个1到n的序列，1不是质数不用加入，2是质数加入，筛掉范围内2的倍数，3是质数加入，筛掉范围内所有三的倍数。以此类推。注意：这种方法耗费了大量的空间换取了时间，因为建立了flag数组，所以一般只适用于10的7次方的规模。（可能有更好的可以节省空间的写法，但我不会）

代码（一个很普通的方法）

import mathdef is_prime(n): if n == 1 or n == 0: return False m = int(math.sqrt(n)+1)for i in range(2,m): if n % i == 0: return False return Truen = int(input()) res = [] for i in range(1,n): if is_prime(i): res.append(i)for i in res: print(i,end=" ") print() print(len(res))

通过截图

文章图片

代码（埃筛法）

import mathdef set_prime(n): flag = [True for i in range(n+1)] # 创建n个标记，False:非质数，True：质数 prime_list = [2] # 存质数 for i in range(3,n,2): # 创建奇数数列,提前筛掉了2 if flag[i]: prime_list.append(i) for j in range(i*2,n+1,i): if j % i == 0: flag[j] = False return prime_listn = int(input()) res = set_prime(n) for i in res: print(i,end=" ") print() print(len(res))

通过截图