【蓝桥杯】简单数论3——素数

素数定义:只能被1和自己整除的正整数。注:1不是素数&＃xff0c;最小素数是2。

判断一个数n是不是素数:当n≤时&＃xff0c;用试除法;n>时&＃xff0c;试除法不够用&＃xff0c;需要用高级算法&＃xff0c;例如Miller_Rabin算法。

试除法&＃xff1a;用[2, n-1]内的所有数去试着除n&＃xff0c;如果都不能整除&＃xff0c;就是素数。

• 优化1&＃xff1a;把[2, n-1]缩小到[2, √n]。证明:若n&＃61; a×b&＃xff0c;其中a≤√n&＃xff0c;b>√n&＃xff0c;如果n有个因子是a&＃xff0c;说明n不是素数&＃xff0c;b不用再试。
• 优化2&＃xff1a;提前算出[2, √n]范围内的所有素数&＃xff0c;用这些素数来除n就行了。埃氏筛用到这一原理。范围[2&＃xff0c;√n]内有多少个素数?在1百万以内&＃xff0c;约有7.8万个素数;在1亿以内&＃xff0c;约有576万个素数&＃xff0c;提高了十几倍的速度。但一般只需要用优化1即可。

from math import*
def is_prime(n): #若n是素数&＃xff0c;返回true
if n &＃61;&＃61; 1: return False #1不是素数
m &＃61; int(sqrt(n)&＃43;1) #sqrt(n)&＃xff0c;也可以这样写n**0.5
for i in range(2, m):
if n % i &＃61;&＃61; 0:
return False #不是素数
return True #是素数

 例题一:选数

lanqiao0J题号753

题目描述

已知 n 个整数 1,2,⋯,x1​,x2​,⋯,xn​&＃xff0c;以及一个整数 k&＃xff08;k&＃xff1c;n&＃xff09;。从 n 个整数中任选 k 个整数相加&＃xff0c;可分别得到一系列的和。例如当 n&＃61;4&＃xff0c;k&＃xff1d;3&＃xff0c;4个整数分别为 3&＃xff0c;7&＃xff0c;12&＃xff0c;19 时&＃xff0c;可得全部的组合与它们的和为&＃xff1a;

3&＃xff0b;7&＃xff0b;12&＃61;22            3&＃xff0b;7&＃xff0b;19&＃xff1d;29            7&＃xff0b;12&＃xff0b;19&＃xff1d;38            3&＃xff0b;12&＃xff0b;19&＃xff1d;34。

现在&＃xff0c;要求你计算出和为素数共有多少种。 例如上例&＃xff0c;只有一种的和为素数&＃xff1a;3&＃xff0b;7&＃xff0b;19&＃xff1d;29。

输入描述

输入格式为&＃xff1a;

第一行&＃xff1a;n,k&＃xff08;1≤n≤20&＃xff0c;k&＃xff1c;n&＃xff09;

第二行&＃xff1a;x1​,x2​,⋯,xn​&＃xff08;1≤xi​≤5×106&＃xff09;

输出描述

一个整数&＃xff08;满足条件的种数&＃xff09;。

输入输出样例

输入

4 3
3 7 12 19


输出

1

先得到从s中选出k个的所有组合&＃xff0c;使用combinations()函数&＃xff0c;然后判断这些组合的和是否为素数。

from math import *
from itertools import * # combinations(s,k)需要导入这个库
def is_prime(n):
if n &＃61;&＃61; 1: return False
m &＃61; int(sqrt(n)&＃43;1)#sqrt(n)可以这样写n**0.5
for i in range(2, m):
if n % i &＃61;&＃61; 0: return False
return True
n, k &＃61; map (int, input ().split())
s &＃61; list (map(int, input ().split()))
cnt &＃61; 0
for e in combinations(s,k): # 从s中选出k个的所有组合
num&＃61; sum(e) #求和
if is_prime (num) &＃61;&＃61; True: cnt&＃43;&＃61;1
print(cnt)
例题二&＃xff1a;笨小猴 

lanqiao0J题号527

题目描述

笨小猴的词汇量很小&＃xff0c;所以每次做英语选择题的时候都很头疼。但是他找到了一种方法&＃xff0c;经试验证明&＃xff0c;用这种方法去选择选项的时候选对的几率非常大&＃xff01;

这种方法的具体描述如下&＃xff1a;假设 maxn 是单词中出现次数最多的字母的出现次数&＃xff0c;minn 是单词中出现次数最少的字母的出现次数&＃xff0c;如果 maxn−minn 是一个质数&＃xff0c;那么笨小猴就认为这是个 Lucky Word&＃xff0c;这样的单词很可能就是正确的答案。

输入描述

输入一行&＃xff0c;是一个单词&＃xff0c;其中只可能出现小写字母&＃xff0c;并且长度小于 100。

输出描述

输出两行&＃xff0c;第一行是一个字符串&＃xff0c;假设输入的的单词是Lucky Word&＃xff0c;那么输出Lucky Word&＃xff0c;否则输出No Answer&＃xff1b;

第二行是一个整数&＃xff0c;如果输入单词是 Lucky Word&＃xff0c;输出 maxn−minn 的值&＃xff0c;否则输出 0。

输入输出样例

示例 1

输入

error


输出

Lucky Word
2


示例 2

输入

Olympic


输出

No Answer
0

模拟,统计每个字母出现的次数s.count(i)&＃xff0c;然后判断maxn-minn是否为素数。

from math import *
def is_prime(n):
if n &＃61;&＃61; 0 or n&＃61;&＃61;1:return False
m &＃61; int(sqrt(n)&＃43;1)
for i in range(2,m):
if n%i &＃61;&＃61; 0: return False
return True
s &＃61; input()
maxn&＃61; -1 # 反向初始化&＃xff08;最大值初始化为最小&＃xff0c;最小值初始化为最大&＃xff09;
minn&＃61; 1000
for i in s: # 找出最最小值
n&＃61;s.count(i)
maxn&＃61;max(maxn,n)
minn&＃61;min(minn,n)
if is_prime(maxn-minn):print("Lucky Word");print(maxn-minn)
else: print("No Answer");print(0)
例题三&＃xff1a; 最大最小公倍数

lanqiao0J题号1510

题目描述

已知一个正整数 N&＃xff0c;问从 1∼N 中任选出三个数&＃xff0c;他们的最小公倍数最大可以为多少。

输入描述

输入一个正整数 N。1≤N≤10^6。

输出描述

输出一个整数表示答案。

输入输出样例

输入

9


输出

504

思路&＃xff1a;贪心

• 贪心题&＃xff0c;从大的数开始选。不过&＃xff0c;简单地把N里面最大的三个数相乘&＃xff0c;N*(N-1)*(N-2)&＃xff0c;并不正确&＃xff0c;需要分析多种情况。
• 最小的公倍数是三个数的质因数相乘&＃xff0c;如果有几个质因数相同&＃xff0c;则比较两数中哪个数的质因数的个数较多。例如6、7、8的最小公倍数&＃xff0c;先分解因子:6&＃61;2×3&＃xff0c;7&＃61;7×1&＃xff0c;8&＃61;2×2×2&＃xff0c;它们的最小公倍数是3×7×2×2×2。
• 大于1的两个相邻整数互质&＃xff0c;它们没有公共的质因数。如果题目是任选二个数&＃xff0c;最大的最小公倍数是N*(N-1)。

对于连续的最大三个整数&＃xff0c;分两种情况:
(1)N是奇数。N、N-1、N-2是奇偶奇&＃xff0c;结论是这三个数两两互质&＃xff0c;三个数的乘积就是最大的最小公倍数。三个数两两互质&＃xff0c;也就是说任意一个质数&＃xff0c;只在N、N-1、N-2中出现一次。连续的三个整数的质因数必有2和3&＃xff0c;奇数N的质因数可能仅有3&＃xff0c;但有且仅有N-1有质因数2。所以N是奇数&＃xff0c;那么N、N-1、N-2互质。

证明&＃xff1a;下面对这两个质数分析:

• 质因数2&＃xff0c;只在N-1中出现。
• 质因数3&＃xff0c;如果在N中出现&＃xff08;设N&＃61;3a&＃xff0c;a为整数&＃xff09;&＃xff0c;就不会在N-1中出现&＃xff08;这要求N-1 &＃61; 3b&＃xff0c;&＃xff0c;n为整数&＃xff0c;N无整数解)&＃xff0c;也不会在N-2中出现&＃xff08;这要求N-2&＃61; 3b&＃xff0c;N无整数解&＃xff09;。

结论&＃xff1a;推广到任何一个质数k&＃xff0c;都只会在N、N-1、N-2中出现一次&＃xff0c;所以三个数互质。

(2&＃xff09;N是偶数。 N的质因数要么有2和3两个质数&＃xff0c;要么有2一个质数

• 质因数2&＃xff0c;N和N-2有公因子2;
• 质因数3&＃xff0c;若设N&＃61; 6a&＃xff0c;N-1&＃61;6b, N-2&＃61;6c。由上面质因数3的分析可知&＃xff0c;质数3只会出现在N中

结论&＃xff1a;如果偶数N中有质因数3&＃xff0c;那么N、N-1、N-2互质&＃xff0c;否则N、N-1、N-3互质&＃xff08;因为只有N有质因数2)。

n &＃61; int(input())
if n <&＃61; 2: print(n)
elif n % 2 !&＃61; 0: # n是奇数
print(n * (n - 1) * (n - 2))
else: # n是偶数
if n % 3 &＃61;&＃61; 0: print((n-1)*(n-2)*(n-3))# n有因数3
else:print (n*(n-1)*(n-3)) # n没有因数3
 2、素数筛

• 素数的筛选:给定n&＃xff0c;求2~n内所有的素数。
• 一个个地判断很慢&＃xff0c;所以用“筛子”筛所有的整数&＃xff0c;把非素数筛掉&＃xff0c;剩下的就是素数。
• 常用两种筛法&＃xff1a;埃氏筛、欧拉筛。

初始队列{2、3&＃xff0c;4&＃xff0c;5&＃xff0c;6&＃xff0c;7&＃xff0c;8&＃xff0c;9&＃xff0c;10&＃xff0c;11&＃xff0c;12&＃xff0c;13&＃xff0c;...&＃xff0c;n}&＃xff0c;操作步骤:
...
(1&＃xff09;输出最小的素数2&＃xff0c;筛掉2的倍数&＃xff0c;得{3&＃xff0c;5&＃xff0c;7&＃xff0c;9&＃xff0c;&＃xff0c;11&＃xff0c;13&＃xff0c;...}

(2&＃xff09;输出最小的素数3&＃xff0c;筛掉3的倍数&＃xff0c;得{5&＃xff0c;7&＃xff0c;11&＃xff0c;13&＃xff0c;...}

(3&＃xff09;输出最小的素数5&＃xff0c;筛掉5的倍数&＃xff0c;得{7&＃xff0c;11&＃xff0c;13&＃xff0c;...}

继续以上步骤&＃xff0c;直到队列为空。

lanqiao0J题号1557​​​​​​​

题目描述

给定一个正整数 N&＃xff0c;请你输出 N 以内&＃xff08;不包含 N&＃xff09;的质数以及质数的个数。

输入描述

输入一行&＃xff0c;包含一个正整数 N。1≤N≤1000

输出描述

共两行。

第 1 行包含若干个素数&＃xff0c;每两个素数之间用一个空格隔开&＃xff0c;素数从小到大输出。

第 2 行包含一个整数&＃xff0c;表示N以内质数的个数。

输入输出样例

输入

10


输出

2 3 5 7
4

• vis[i]记录数i的状态&＃xff0c;若vis[i]&＃61;1,表示它被筛掉&＃xff0c;不是素数。
• 用prime[ ]存放素数,prime[0]是第一个素数2。
• E_sieve(n)函数用来做筛除的数2、3、5......等&＃xff0c;最多到就可以了。例如&＃xff0c;求n &＃61;100以内的素数&＃xff0c;用2、3、5、7筛就足够了。原理和试除法一样:非素数k&＃xff0c;必定可以被一个小于等于的素数整除,被筛掉。

from math import *
def E_sieve(n) : # 埃氏筛
for i in range (2,int (sqrt(n)&＃43;1)):
if not vis[i]: # 没有被筛过&＃xff0c;是素数
for j in range(i*i, n&＃43;1,i): # 开始筛该素数的倍数
vis[j] &＃61; 1
k&＃61;0
for i in range (2, n&＃43;1): #存素数
if not vis[i]: # 没有被筛
prime[k] &＃61; i # 是素数。可以不需要用prime存&＃xff0c;直接打印即可print(vis[i],end&＃61;" ")
k &＃43;&＃61; 1
return k
N&＃61; int(1e6)
prime &＃61;[0]*N
vis &＃61; [0]*N
n &＃61; int (input())
k&＃61; E_sieve(n-1)
for i in range (0,k): print (prime[i], end&＃61;" ")
print ()
print (k)
 3、区间素数

埃氏筛法求[2, n]内的素数&＃xff0c;只能解决规模n<的问题。如果n更大&＃xff0c;在某些情况下&＃xff0c;也可以用埃氏筛法来处理&＃xff0c;这就是大区间素数的计算。
把埃氏筛法扩展到求区间[a, b]的素数&＃xff0c;a&＃xff0c;b-a≤。

方法:先用埃氏筛法求[2,]内的素数&＃xff0c;然后用这些素数来筛[a,b]区间的素数

lanqiao0J题号1558

题目描述

给定一个区间 [a,b]&＃xff0c;请你求出该区间内有多少个素数。

输入描述

输入共一行&＃xff0c;包含两个整数 a,b。

2≤a≤b≤&＃xff0c;b−a≤1000000

输出描述

输出一个整数&＃xff0c;表示答案。

输入输出样例

输入

2 6


输出

3

题解&＃xff1a; 

本题a&＃xff0c;b<&＃61;  ,不能直接定义一个vis[N]&＃xff0c;N&＃61;来表示[0,b]内的每个数字&＃xff0c;空间太大。
只能定义区间大小的空间&＃xff0c;即N&＃61;1000000。

from math import *
def seg_sieve(a, b):
for i in range(2,int(sqrt(b))&＃43;1): # 先用埃氏筛求2~√n的素数
if vis[i]&＃61;&＃61; True: # 是素数
for j in range(i*i,int(sqrt(b)),i):
vis[j]&＃61;False
# 再求[a, b]的素数
for j in range(max(2,(a&＃43;i-1)//i)*i, b&＃43;1,i): # 难点&＃xff1a;处理起点&＃xff1a;max(2,(a&＃43;i-1)//i)*i&＃xff0c;从当前素数i的倍数开始筛
seg_prime[j-a]&＃61;False
num&＃61; 0
# 统计[a, b]的素数个数
for i in range(0, b-a&＃43;1):
if seg_prime[i]:
prime[num] &＃61; i&＃43;a
num &＃43;&＃61; 1
print(num)
N &＃61; 1000005 # 稍微大一点&＃xff08;保险)
vis &＃61; [True]*N # 标记[2, sqrt(b)]是否为素数
prime &＃61; [0]*N # 存[a, b]的素数
seg_prime &＃61; [True] * N # 标记[a, b]是否为素数
a, b &＃61; map(int,input ().split())
seg_sieve(a,b)
4、分解质因子

任何一个正整数n都可以唯一地分解为有限个素数的乘积&＃xff1a;&＃xff0c;其中都是正整数&＃xff0c;都是素数且从小到大。
分解质因子也可以用试除法。求n的质因子:
(1)第一步&＃xff0c;求最小质因子。逐个检查从2到的所有素数&＃xff0c;如果它能整除n&＃xff0c;就是最小质因子。然后连续用除n&＃xff0c;目的是去掉n中的&＃xff0c;得到。

 (2&＃xff09;第二步&＃xff0c;再找的最小质因子。逐个检查从p,到的所有素数。从开始试除&＃xff0c;是因为没有比小的素因子&＃xff0c;而且的因子也是n的因子。

 (3&＃xff09;继续以上步骤&＃xff0c;直到找到所有质因子。

题目描述

给定一个区间 [a,b]&＃xff0c;请你求出区间 [a,b] 中所有整数的质因数分解。

输入描述

输入共一行&＃xff0c;包含两个整数 a,b。

2≤a≤b≤10000。 

输出描述

每行输出一个数的分解&＃xff0c;形如 k&＃61;a1​×a2​×a3​⋯(a1​≤a2​≤a3​⋯&＃xff0c;k也是从小到大的)(具体可看样例)

输入输出样例

输入

3 10


输出

3&＃61;3
4&＃61;2*2
5&＃61;5
6&＃61;2*3
7&＃61;7
8&＃61;2*2*2
9&＃61;3*3
10&＃61;2*5

题解&＃xff1a;

直接对每个数进行分解,然后打印出它的因数。

def s(x):#返回x的第一个因子
for i in range(2,int(x**0.5)&＃43;1):
if x%i&＃61;&＃61;0:return i
return x # 若没有找到因子&＃xff0c;返回本身
a, b &＃61; map(int,input ().split())
for x in range(a, b&＃43;1):
print(x,end&＃61;"") ; print( &＃39;&＃61;&＃39;, end&＃61;"")
while x!&＃61;1:
ans &＃61; s(x) # 求最小质因数
if x/ans !&＃61; 1: print(ans, end&＃61;"") ; print(&＃39;*&＃39;, end&＃61;"")
else:print (int(ans)) # 质因子是本身&＃xff0c;直接输出
x /&＃61;ans # 除掉最小质因子&＃xff0c;继续找下一个最小质因子
例题七&＃xff1a;数的拆分

2022年第十三届省赛lanqiao0J题号2090

问题描述

给定 T 个正整数 ai​, 分别问每个 ai​ 能否表示为 的形式, 其中 x1​,x2​ 为正整数, y1​,y2​ 为大于等于 2 的正整数。

输入格式

输入第一行包含一个整数 T 表示洵间次数。

接下来 T 行, 每行包含一个正整数 ai​ 。

输出格式

对于每次询问, 如果 ai​ 能够表示为题目描述的形式则输出 yes, 否则输出 no.

样例输入

7
2
6
12
4
8
24
72


样例输出

no
no
no
yes
yes
no
yes


样例说明

第 4,5,74,5,7 个数分别可以表示为:

a4​&＃61;

a5​&＃61;

a7​&＃61;

评测用例规模与约定

对于 10%1 的评测用例, 1≤T≤200,ai​≤10^9;

对于 30% 的评测用例, 1≤T≤300,ai​≤10^18;

对于 60% 的评测用例, 1≤T≤10000,ai​≤10^18;

对于所有评测用例, 1≤T≤100000,1≤ai​≤10^18

 题解&＃xff1a;

例:24不行&＃xff0c;因为24&＃61;。72可以&＃xff0c;因为72&＃61;。
数据规模ai≤&＃xff0c;即使用之前的优化方法&＃xff1a;遍历2~&＃xff08;即2~&＃xff09;也是不能通过所有测评用例。​​​​​​​

对a进行素因子分解a&＃61;
重点&＃xff1a;题目要求≥2&＃xff0c;拆分。可以保证所有均有非负整数解。
对于任意k>1都有非负整数解&＃xff0c;例如:

• k %3&＃61;0&＃xff0c;&＃61;0&＃xff0c;&＃61; k/3
• k %3&＃61;1&＃xff0c;&＃61;2&＃xff0c;&＃61;(k-4)/3
• k %3&＃61;2&＃xff0c;,&＃61; 1&＃xff0c;&＃61;(k-2)/3

问题变成a是否能分解为&＃xff0c;检测每个是否大于等于2&＃xff0c;只要大于等于2&＃xff0c;就可以按对应的k分配到

本题a≤10^18&＃xff0c;所以&＃xff0c;当素因子p >4000时​​​​​​​&＃xff0c;只需要暴力判断4000以内的素因子&＃xff0c;对于大于4000的p&＃xff0c;指数只能是2、3、4&＃xff0c;判断是否为平方数或立方数即可。

时间复杂度:
用埃氏筛预计算p&＃61;.4000以内的素数&＃xff0c;O(p^2)。
然后进行判断&＃xff0c;O(T*550)&＃xff0c;550是4000以内的素数个数。

from math import *
N &＃61; 4000
prime &＃61; [0]*N
vis &＃61; [0]*N
cnt &＃61; 0
def E_sieve(): # 预计算4000以内的素数
global cnt
for i in range(2,N):
if not vis[i]: cnt&＃43;&＃61;1; prime[cnt] &＃61; i
for j in range(i*i,N,i):vis[j] &＃61; 1
def solve() :
a &＃61; int(input())
for i in range (1, cnt&＃43;1): # 遍历4000以内所有素数
c &＃61; 0 # 统计因子个数
while a % prime[i] &＃61;&＃61; 0: # 能被整除&＃xff0c;
a/&＃61;prime[i]
c&＃43;&＃61;1 # 次方&＃43;1
if c&＃61;&＃61;1: print("no"); return # 次方数为1&＃xff0c;不合题意
k &＃61; int(sqrt(a))
if k*k &＃61;&＃61; a: print("yes"); return # 检查n是否为平方数
k &＃61; int (pow(a,1/3))
if k*k*k&＃61;&＃61;a: print("yes"); return # 检查n是否为立方数
print("no")
E_sieve()
T&＃61;int(input())
for i in range(T): solve()