devbox
花生_TL007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【蓝桥杯】简单数论3——素数_给定一个正整数n,请你输出n以内(不包含n)的质数以及质数的个数。

作者：花生_TL007 | 2024-04-18 16:07:30

赞

踩

给定一个正整数n,请你输出n以内(不包含n)的质数以及质数的个数。

1、素数判断

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

判断一个数n是不是素数:当n≤10^{14}时，用试除法;n>10^{14}时，试除法不够用，需要用高级算法，例如Miller_Rabin算法。

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

  • 优化1：把[2, n-1]缩小到[2, √n]。证明:若n= a×b，其中a≤√n，b>√n，如果n有个因子是a，说明n不是素数，b不用再试。
  • 优化2：提前算出[2, √n]范围内的所有素数，用这些素数来除n就行了。埃氏筛用到这一原理。范围[2，√n]内有多少个素数?在1百万以内，约有7.8万个素数;在1亿以内，约有576万个素数，提高了十几倍的速度。但一般只需要用优化1即可。
  1. from math import*
  2. def is_prime(n):                #若n是素数，返回true
  3.     if n == 1: return False     #1不是素数
  4.     m = int(sqrt(n)+1)          #sqrt(n)，也可以这样写n**0.5
  5.     for i in range(2, m):
  6.         if n % i == 0: 
  7.             return False        #不是素数
  8.     return True                 #是素数

 例题一:选数

lanqiao0J题号753

题目描述

已知 n 个整数 1,2,⋯,x1​,x2​,⋯,xn​，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：

3＋7＋12=22            3＋7＋19＝29            7＋12＋19＝38            3＋12＋19＝34。

现在，要求你计算出和为素数共有多少种。 例如上例，只有一种的和为素数：3＋7＋19＝29。

输入描述

输入格式为：

第一行：n,k（1≤n≤20，k＜n）

第二行：x1​,x2​,⋯,xn​（1≤xi​≤5×106）

输出描述

一个整数（满足条件的种数）。

输入输出样例

输入

  1. 4 3
  2. 3 7 12 19

输出

1

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

  1. from math import *
  2. from itertools import * # combinations(s,k)需要导入这个库
  3. def is_prime(n):
  4.     if n == 1: return False
  5.     m = int(sqrt(n)+1)#sqrt(n)可以这样写n**0.5
  6.     for i in range(2, m):
  7.         if n % i == 0: return False
  8.     return True
  9. n, k = map (int, input ().split())
  10. s = list (map(int, input ().split()))
  11. cnt = 0
  12. for e in combinations(s,k): # 从s中选出k个的所有组合
  13.     num= sum(e)             #求和
  14.     if is_prime (num) == True: cnt+=1
  15. print(cnt)

例题二：笨小猴 

lanqiao0J题号527

题目描述

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

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

输入描述

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

输出描述

输出两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出Lucky Word，否则输出No Answer；

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

输入输出样例

示例 1

输入

error

输出

  1. Lucky Word
  2. 2

示例 2

输入

Olympic

输出

  1. No Answer
  2. 0

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

  1. from math import *
  2. def is_prime(n):
  3.     if n == 0 or n==1:return False
  4.     m = int(sqrt(n)+1)
  5.     for i in range(2,m):
  6.         if n%i == 0:  return False
  7.     return True
  8. s = input()
  9. maxn= -1    # 反向初始化（最大值初始化为最小，最小值初始化为最大）
  10. minn= 1000
  11. for i in s: # 找出最最小值
  12.     n=s.count(i)
  13.     maxn=max(maxn,n)
  14.     minn=min(minn,n)
  15. if is_prime(maxn-minn):print("Lucky Word");print(maxn-minn)
  16. else:                  print("No Answer");print(0)

例题三： 最大最小公倍数

lanqiao0J题号1510

题目描述

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

输入描述

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

输出描述

输出一个整数表示答案。

输入输出样例

输入

9

输出

504

思路：贪心

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

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

证明：下面对这两个质数分析:

  • 质因数2，只在N-1中出现。
  • 质因数3，如果在N中出现（设N=3a，a为整数），就不会在N-1中出现（这要求N-1 = 3b，，n为整数，N无整数解)，也不会在N-2中出现（这要求N-2= 3b，N无整数解）。

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

(2）N是偶数。 N的质因数要么有2和3两个质数，要么有2一个质数

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

结论：如果偶数N中有质因数3，那么N、N-1、N-2互质，否则N、N-1、N-3互质（因为只有N有质因数2)。

  1. n = int(input())
  2. if n <= 2: print(n)
  3. elif n % 2 != 0:  # n是奇数
  4.     print(n * (n - 1) * (n - 2))
  5. else:             # n是偶数
  6.     if n % 3 == 0: print((n-1)*(n-2)*(n-3))# n有因数3
  7.     else:print (n*(n-1)*(n-3))             # n没有因数3

 2、素数筛

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

2.1埃氏筛

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

(2）输出最小的素数3，筛掉3的倍数，得{5，7，11，13，...}

(3）输出最小的素数5，筛掉5的倍数，得{7，11，13，...}

继续以上步骤，直到队列为空。

例题四：质数（模板题）

lanqiao0J题号1557

题目描述

给定一个正整数 N，请你输出 N 以内（不包含 N）的质数以及质数的个数。

输入描述

输入一行，包含一个正整数 N。1≤N≤1000

输出描述

共两行。

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

第 2 行包含一个整数，表示N以内质数的个数。

输入输出样例

输入

10

输出

  1. 2 3 5 7
  2. 4
  • vis[i]记录数i的状态，若vis[i]=1,表示它被筛掉，不是素数。
  • 用prime[ ]存放素数,prime[0]是第一个素数2。
  • E_sieve(n)函数用来做筛除的数2、3、5......等，最多到\sqrt{n}就可以了。例如，求n =100以内的素数，用2、3、5、7筛就足够了。原理和试除法一样:非素数k，必定可以被一个小于等于的素数整除,被筛掉。
  1. from math import *
  2. def E_sieve(n) : # 埃氏筛
  3.     for i in range (2,int (sqrt(n)+1)):
  4.         if not vis[i]:    # 没有被筛过，是素数
  5.             for j in range(i*i, n+1,i):    # 开始筛该素数的倍数
  6.                 vis[j] = 1
  7.     k=0
  8.     for i in range (2, n+1):   #存素数
  9.         if not vis[i]:    # 没有被筛
  10.             prime[k] = i  # 是素数。可以不需要用prime存，直接打印即可print(vis[i],end=" ")
  11.             k += 1
  12.     return k
  13. N= int(1e6)
  14. prime =[0]*N
  15. vis = [0]*N
  16. n = int (input())
  17. k= E_sieve(n-1)
  18. for i in range (0,k): print (prime[i], end=" ")
  19. print ()
  20. print (k)

 3、区间素数

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

方法:先用埃氏筛法求[2,\sqrt{n}]内的素数，然后用这些素数来筛[a,b]区间的素数

例题五：找素数(模板题)

lanqiao0J题号1558

题目描述

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

输入描述

输入共一行，包含两个整数 a,b。

2≤a≤b≤2^{31}，b−a≤1000000

输出描述

输出一个整数，表示答案。

输入输出样例

输入

2 6

输出

3

题解： 

本题a，b<= 2^{31} ,不能直接定义一个vis[N]，N=2^{31}来表示[0,b]内的每个数字，空间太大。
只能定义区间大小的空间，即N=1000000。

代码

  1. from math import *
  2. def seg_sieve(a, b):
  3.     for i in range(2,int(sqrt(b))+1):   # 先用埃氏筛求2~√n的素数
  4.         if vis[i]== True:                      # 是素数
  5.             for j in range(i*i,int(sqrt(b)),i):
  6.                 vis[j]=False
  7.             # 再求[a, b]的素数
  8.             for j in range(max(2,(a+i-1)//i)*i, b+1,i): # 难点：处理起点：max(2,(a+i-1)//i)*i，从当前素数i的倍数开始筛
  9.                 seg_prime[j-a]=False
  10.     num= 0
  11.     # 统计[a, b]的素数个数
  12.     for i in range(0, b-a+1):
  13.         if seg_prime[i]:
  14.             prime[num] = i+a
  15.             num += 1
  16.     print(num)
  17. N = 1000005 # 稍微大一点（保险)
  18. vis = [True]*N          # 标记[2, sqrt(b)]是否为素数
  19. prime = [0]*N           # 存[a, b]的素数
  20. seg_prime = [True] * N  # 标记[a, b]是否为素数
  21. a, b = map(int,input ().split())
  22. seg_sieve(a,b)

4、分解质因子

任何一个正整数n都可以唯一地分解为有限个素数的乘积：n=p_1^{c1}p_2^{c2}...p_m^{cm}，其中c_i都是正整数，p_i都是素数且从小到大。
分解质因子也可以用试除法。求n的质因子:
(1)第一步，求最小质因子p_1。逐个检查从2到\sqrt{n}的所有素数，如果它能整除n，就是最小质因子。然后连续用p_1除n，目的是去掉n中的p_1，得到n_1。

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

 (3）继续以上步骤，直到找到所有质因子。

例题六：寻找质因子 

题目描述

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

输入描述

输入共一行，包含两个整数 a,b。

2≤a≤b≤10000。 

输出描述

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

输入输出样例

输入

3 10

输出

  1. 3=3
  2. 4=2*2
  3. 5=5
  4. 6=2*3
  5. 7=7
  6. 8=2*2*2
  7. 9=3*3
  8. 10=2*5

题解：

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

  1. def s(x):#返回x的第一个因子
  2.     for i in range(2,int(x**0.5)+1):
  3.         if x%i==0:return i
  4.     return x        # 若没有找到因子，返回本身
  5. a, b = map(int,input ().split())
  6. for x in range(a, b+1):
  7.     print(x,end="") ; print( '=', end="")
  8.     while x!=1:
  9.         ans = s(x)    # 求最小质因数
  10.         if x/ans != 1: print(ans, end="") ; print('*', end="")
  11.         else:print (int(ans)) # 质因子是本身，直接输出
  12.         x /=ans               # 除掉最小质因子，继续找下一个最小质因子

例题七：数的拆分

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

问题描述

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

输入格式

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

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

输出格式

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

样例输入

  1. 7
  2. 2
  3. 6
  4. 12
  5. 4
  6. 8
  7. 24
  8. 72

样例输出

  1. no
  2. no
  3. no
  4. yes
  5. yes
  6. no
  7. yes

样例说明

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

a4​=2^2*1^2

a5​=2^3*1^2

a7​=2^3*3^2

评测用例规模与约定

对于 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

 题解：

例:24不行，因为24=3^1*2^3。72可以，因为72=2^3*3^2。
数据规模ai≤10^{18}，即使用之前的优化方法：遍历2~\sqrt{a_i}（即2~10^9）也是不能通过所有测评用例。

对a进行素因子分解a= p^{q1}_1p^{q2}_2
重点：题目要求qi≥2，拆分q_i=k_1y_1+k_2y_2,k_1,k_2\geq 0,y_1,y_2\geq 2。y_1=2,y_2=3可以保证所有q_i\geq 2均有非负整数解。
q_i=ky_1+ ky_2= 2k_1+3k_2= k对于任意k>1都有非负整数解，例如:

  • k %3=0，k_1=0，k2= k/3
  • k %3=1，k_1=2，k2=(k-4)/3
  • k %3=2，k_1,= 1，k2=(k-2)/3

问题变成a是否能分解为x_1^2x_2^3，检测每个qi是否大于等于2，只要大于等于2，就可以按对应的k分配到x_1,x_2

本题a≤10^18，所以x_1^2x_2^3=10^{18}，当素因子p >4000时p^5 \geqslant 10^{18}，只需要暴力判断4000以内的素因子，对于大于4000的p，指数只能是2、3、4，判断是否为平方数或立方数即可。

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

  1. from math import *
  2. N = 4000
  3. prime = [0]*N
  4. vis = [0]*N
  5. cnt = 0
  6. def E_sieve(): # 预计算4000以内的素数
  7.     global cnt
  8.     for i in range(2,N):
  9.         if not vis[i]: cnt+=1; prime[cnt] = i
  10.         for j in range(i*i,N,i):vis[j] = 1
  11. def solve() :
  12.     a = int(input())
  13.     for i in range (1, cnt+1):   # 遍历4000以内所有素数
  14.         c = 0                    # 统计因子个数
  15.         while a % prime[i] == 0: # 能被整除，
  16.             a/=prime[i]
  17.             c+=1                 # 次方+1
  18.         if c==1: print("no"); return   # 次方数为1，不合题意
  19.     k = int(sqrt(a))
  20.     if k*k == a: print("yes"); return  # 检查n是否为平方数
  21.     k = int (pow(a,1/3))
  22.     if k*k*k==a: print("yes"); return   # 检查n是否为立方数
  23.     print("no")
  24. E_sieve()
  25. T=int(input())
  26. for i in range(T): solve()

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/446934
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号