vip广告网站建设,网站权重是怎么提升的,加盟招商推广网站,wordpress公司网站模板报名明年4月蓝桥杯软件赛的同学们#xff0c;如果你是大一零基础#xff0c;目前懵懂中#xff0c;不知该怎么办#xff0c;可以看看本博客系列#xff1a;备赛20周合集 20周的完整安排请点击#xff1a;20周计划 每周发1个博客#xff0c;共20周。 在QQ群上交流答疑如果你是大一零基础目前懵懂中不知该怎么办可以看看本博客系列备赛20周合集 20周的完整安排请点击20周计划 每周发1个博客共20周。 在QQ群上交流答疑 文章目录 1. 模运算2. 快速幂3. 素数3.1 小素数的判定3.2 素数筛3.3 质因数分解 第14周: 快速幂素数 蓝桥杯肯定考数学例如数论、几何、概率论、组合数学等。这里介绍几个简单、常见的知识点。
1. 模运算 模运算是大数运算中的常用操作。如果一个数太大无法直接输出或者不需要直接输出可以把它取模后缩小数值再输出。 [ 模是Mod的音译读作mó。Mod意为求余。] 定义取模运算为a除以m的余数记为a mod m a % m 正整数取模的结果满足 0 ≤ a mod m ≤ m-1其含义是用给定的m限制计算结果的范围。若m 10就是取a的个位数若m 2余数为0表示a为偶数否则a为奇数。 一般的求余都是正整数的操作如果是负数求余不同的编程语言结果可能不同下面给出三种语言的例子。 C和Java例子15 % 3输出22(-5) % (-3)输出-235 % (-3)输出24(-5) % 3输出-2。计算规则是先按正整数求余然后加上符号符号和被除数一样。 Python的负数求余有点奇怪例如1123 % 10输出32123 %(-10)输出-7。原因是Python的求余是向下对齐的。 取模操作满足以下性质 加(ab) mod m ((a mod m) (b mod m)) mod m。如果没有限制a、b的正负C代码中左右可能符号相反、大小相差m。但是Python代码不存在这个问题。 减(a - b) mod m ((a mod m) – (b mod m)) mod m。C代码中左右可能符号相反、大小相差m。但是Python代码不存在这个问题。 乘(a × b) mod m ((a mod m) × (b mod m)) mod m 然而对除法取模进行类似操作是错误的(a/b) mod m ((a mod m)/(b mod m)) mod m 例如(100/50) mod 20 2(100 mod 20) / (50 mod 20) mod 20 0两者不相等。
2. 快速幂 一个常见的考点是做幂运算 a n a^n an即n个a相乘n一般极大例如 n 1 0 15 n10^{15} n1015。如果直接计算 a n a^n an逐个相乘那么要乘n次肯定会超时。另外由于 a n a^n an极大一般会取模求余数再输出。 例题快速幂 问题描述给你三个整数anm求 a n a^n an mod m。 输入输入只有一行三个整数分别代表anm。0≤a, b 2 31 2^{31} 231ab02≤p 2 31 2^{31} 231。 输出输出一行一个字符串 a^n mod ms其中anm分别为题目给定的值s为运算结果。 输入样例 2 10 9 输出样例 2^10 mod 97 容易想到一种很快的办法先算 a 2 a^2 a2然后再算平方 a 2 2 {a^2}^2 a22再继续平方 a 2 2 2 {{a^2}^2}^2 a222…总共只需要算O(logn)次就得到了 a n a^n an。当 n 1 0 15 n10^{15} n1015时logn ≈ 50计算量极小。不过这里的n需要是2的倍数如果不是2的倍数呢 下面先用分治法实现这个思路。分治法是一种“从宏观到微观”的处理方法。在快速幂这个问题中把规模为n的大问题分解成两个完全一样的规模为n/2的子问题子问题再继续分解直到最后n1此时直接返回a即可。 下面是 a n % m a^n \% m an%m的分治法代码。注意第6、8、9行中”%m”的取模操作如果不取模会导致溢出。 C代码
#includebits/stdc.h
using namespace std;
typedef long long ll; //用long long比int的范围大
ll fastPow(ll a, ll n,ll m){ //a^n % mif(n 0) return 1; //特判 a^0 1if(n 1) return a % m;ll t fastPow(a, n/2, m); //分治if(n%2 1) return (t % m * t % m) * a % m; //奇数个aelse return t % m * t % m ; //偶数个a
}
int main(){ll a,n,m; cinanm; printf(%lld^%lld mod %lld%lld,a,n,m,fastPow(a,n,m));return 0;
}java代码
import java.util.Scanner;
public class Main {public static long fastPow(long a, long n, long m) {if (n 0) return 1;if (n 1) return a % m;long t fastPow(a, n / 2, m);if (n % 2 1) return (t % m * t % m) * a % m;else return t % m * t % m;}public static void main(String[] args) {Scanner sc new Scanner(System.in);long a sc.nextLong();long n sc.nextLong();long m sc.nextLong();System.out.printf(%d^%d mod %d%d, a, n, m, fastPow(a, n, m));}
}python代码
def fastPow(a, n, m):if n 0: return 1if n 1: return a % mt fastPow(a, n//2, m)if n % 2 1: return (t * t) * a % melse: return t * t % m
a, n, m map(int, input().split())
print(str(a) ^ str(n) mod str(m) str(fastPow(a, n, m))) 读者可以用n7来模拟代码的计算过程了解它是如何处理n的特别是n为奇数的情况。 这个代码已经很不错了不过标准的快速幂有更好的方法用位运算实现。位运算实现快速幂的效率和分治法的效率一样都是O(logn)的。 基于位运算的快速幂用到了二进制数的性质二进制数每一位的权值是按2的倍数递增的。下面以 a 11 a^{11} a11为例说明如何用倍增法做快速幂。 1幂次与二进制的关系。把 a 11 a^{11} a11分解成幂 a 8 a^8 a8、 a 2 a^2 a2、 a 1 a^1 a1的乘积 a 11 a 8 2 1 a 8 × a 2 × a 1 a^{11} a^{821} a^8 × a^2 × a^1 a11a821a8×a2×a1。其中 a 1 、 a 2 、 a 4 、 a 8 a^1、a^2、a^4、a^8 a1、a2、a4、a8…的幂次都是2的倍数所有的幂ai都是倍乘关系可以逐级递推在代码中用 a * a实现。 2幂次用二进制分解。如何把11分解为821利用数的二进制的特征 n 1 1 10 101 1 2 2 3 2 1 2 0 8 2 1 n 11_{10} 1011_2 2^32^12^0 821 n111010112232120821只需要把n按二进制逐位处理就可以了。 3如何跳过那些没有的幂次例如1011需要跳过 a 4 a^4 a4。做个判断即可用二进制的位运算实现用到了n 1和n 1这两个位运算。 n 1取n的最后一位并且判断这一位是否需要跳过。 n 1把n右移一位目的是把刚处理过的n的最后一位去掉。 以 n 101 1 2 n1011_2 n10112为例步骤如下 n1011计算n 1得1最后一位是1对应 a1。n 1右移一位更新n101。 n101计算n 1得1最后一位是1对应 a2。n 1更新n10。 n10计算n 1得0最后一位是0跳过a4。n 1更新n1。 n1计算n 1得1最后一位是1对应a8。n 1更新n0结束。 下面是快速幂的代码。 C代码
#includebits/stdc.h
using namespace std;
typedef long long ll; //用long long比int的范围大
ll fastPow(ll a, ll n, ll m){ll ans 1;a % m; //能在一定程度上防止下面的a*a越界while(n) {if(n 1) ans (ans*a) % m; //取模a (a*a) % m; //取模n 1;}return ans;
}
int main(){ll a,n,m; cin a n m; //m是模printf(%lld^%lld mod %lld%lld,a,n,m,fastPow(a,n,m));return 0;
}
java代码
java
import java.util.Scanner;
public class Main {public static long fastPow(long a, long n, long m) {long ans 1;a % m;while (n 0) {if ((n 1) 1) ans (ans * a) % m;a (a * a) % m;n 1;}return ans;}public static void main(String[] args) {Scanner sc new Scanner(System.in);long a sc.nextLong();long n sc.nextLong();long m sc.nextLong();System.out.printf(%d^%d mod %d%d, a, n, m, fastPow(a, n, m));}
}python代码
def fastPow(a, n, m):ans 1while n:if n 1: ans * aa (a * a) % mn 1return ans % m
a, n, m map(int, input().split())
print(str(a) ^ str(n) mod str(m) str(fastPow(a, n, m)))再做一题。 越狱 问题描述监狱有n个房间每个房间关押一个犯人有m种宗教每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同就可能发生越狱求有多少种状态可能发生越狱。答案对100,003取模。 输入输入只有一行两个整数分别代表宗教数m和房间数n。1≤m≤ 1 0 8 10^8 108, 1≤n≤ 1 0 12 10^{12} 1012。 输出输出一行一个整数代表答案。 输入样例 2 3 输出样例 6 这是一道简单的组合数学问题。直接算越狱的方案数不方便可以用总方案数减去不越狱的方案数就是答案。 1总方案数。一个房间可以有m种宗教所以n个房间一共有 m n m^n mn种方案。 2不越狱的方案数就是任意两个相邻房间都不同的方案数。第1间有m种宗教第2间不能和第1间相同所以有m-1种第3间还是有m-1种因为它不能和第2间相同但是可以和第1间相同第4间、第5间、…、第n间也都是m-1种。所以不越狱的方案数一共是 m ( m − 1 ) n − 1 m(m-1)^{n-1} m(m−1)n−1。 答案是 m n − m ( m − 1 ) n − 1 m^n-m(m-1)^{n-1} mn−m(m−1)n−1因为n很大需要用快速幂计算。下面的代码注意17~19行的取模处理。 C代码
#includebits/stdc.h
using namespace std;
typedef long long ll; //用long long比int的范围大
ll fastPow(ll a, ll n, ll m){ll ans 1;a % m; //能在一定程度上防止下面的a*a越界while(n) {if(n 1) ans (ans*a) % m; //取模a (a*a) % m; //取模n 1;}return ans;
}
int main(){ll n,m; cin m n;ll mod 100003;ll ans fastPow(m,n,mod) - m%mod * fastPow(m-1,n-1,mod)%mod;if(ans0) ans mod; //ans可能是负的变为正数ans % mod;cout ans;return 0;
}java代码
import java.util.Scanner;
public class Main {public static long fastPow(long a, long n, long m) {long ans 1;a % m;while (n 0) {if ((n 1) 1) ans (ans * a) % m;a (a * a) % m;n 1;}return ans;}public static void main(String[] args) {Scanner sc new Scanner(System.in);long m sc.nextLong();long n sc.nextLong();long mod 100003;long ans fastPow(m, n, mod) - (m % mod) * fastPow(m - 1, n - 1, mod) % mod;if (ans 0) ans mod;ans % mod;System.out.println(ans);}
}python代码
def fastPow(a, n, m):ans 1while n:if n 1: ans * aa (a * a) % mn 1return ans % m
m, n map(int, input().split())
mod 100003
ans fastPow(m, n, mod) - m * fastPow(m - 1, n - 1, mod) % mod
if ans 0: ans mod
ans % mod
print(ans)3. 素数 素数质数是数论的基础内容也是算法竞赛的常考知识点。下面介绍素数的判定、筛选、质因数分解的方法和代码。
3.1 小素数的判定 素数定义只能被1和自己整除的正整数。前20个素数是2、3、5、7、11、13、17、19、23、29、31、3741、4347、53、59、61、67、71。素数的分布并不稀疏小于一亿的素数有576万个。 如何判断一个数n是不是素数当 n ≤ 1 0 12 n ≤ 10^{12} n≤1012时用试除法用[2, n-1]内的所有数去试着除n如果都不能整除就是素数。 很容易发现试除法可以优化把 [ 2 , n − 1 ] [2, n-1] [2,n−1]缩小到 [ 2 , n ] [2,\sqrt{n}] [2,n ]。因为如果n不是素数那么它肯定有一个≤ n \sqrt{n} n 的因子证明如下若na×b设a≤b那么肯定有a≤ n \sqrt{n} n 。经过这个优化后试除法的计算复杂度是O( n \sqrt{n} n ) n ≤ 1 0 12 n ≤ 10^{12} n≤1012时够用。下面是代码。 C代码
bool is_prime(long long n){if(n 1) return false; //1不是素数for(long long i2; i sqrt(n); i)if(n % i 0) return false; //能整除不是素数return true; //是素数
}java代码
import java.util.Scanner;
public class Main {public static boolean isPrime(long n) {if (n 1) return false;for (long i 2; i Math.sqrt(n); i)if (n % i 0) return false; return true;}public static void main(String[] args) {Scanner sc new Scanner(System.in);long n sc.nextLong();if (isPrime(n)) System.out.println(is prime);else System.out.println(not prime);}
}python代码
import math
def is_prime(n):if n 1: return Falsefor i in range(2, int(math.sqrt(n)) 1): # sqrt(n)或n**0.5if n % i 0: return Falsereturn True
n int(input())
if is_prime(n): print(is prime)
else: print(not prime)试除法还可以继续优化。 [ 2 , n ] [2,\sqrt{n}] [2,n ]可以继续缩小如果提前算出 [ 2 , n ] [2,\sqrt{n}] [2,n ]内的所有素数那么用这些素数来除n就行了因为 [ 2 , n ] [2,\sqrt{n}] [2,n ]中的合数已经被素数除过了。下一节的埃氏筛法就用到这一原理。 选数 问题描述已知n 个整数a1、a2、…、an以及1个整数k(kn)。从n个整数中任选k个整数相加可分别得到一系列的和。例如当n 4, k 34个整数分别为3、7、12、19时可得全部的组合与它们的和为 371222 371929 7121938 3121934 现在要求你计算出和为素数共有多少种。 例如上例只有一种的和为素数:371929。 输入第一行两个空格隔开的整数n, k(1≤n≤ 20kn)。第二行n个整数分别为a1、a2、…、an1≤ai≤5×106。 输出输出一个整数表示种类数。 输入样例 4 3 3 7 12 19 输出样例 1 本题是一道简单的综合题DFS素数判定。先用DFS从n个数中任选k个然后求和并判断是否为素数。 从n个数中选k个且这k个数没有顺序关系这是组合问题。选数的思路是 1选第1个数这个数可以是n个数中的任何一个设选了ai。i从1到n遍历。 2选第2个数此时选位置i后面的数因为这样做可以避免重复。例如样例的{3, 7, 12, 19}若当前的组合选了{3, 12}那么下一次只能选后面的19不能回头选7这样会重复因为{3, 7, 12}这个组合在前面已经选过了。 3按上述方法选其他数直到满k个。 下面的代码请注意DFS是如何执行的。第18行dfs()继续选下一个数并且下一个数的位置在已经选的数后面。 C代码
#includebits/stdc.h
using namespace std;
int n,k;
int a[25];
int ans; //如果担心 int不够可以改为 long long
bool is_prime(int s){ //判断s是否为素数。s很小用int够了if(s 1) return false;for(int i2; i sqrt(s); i)if(s % i 0) return false;return true;
}
void dfs(int cnt, int sum, int p){ //选了cnt个,和为sum;下一个从a[p]开始选if(cnt k){ //已经选了k个if(is_prime(sum)) ans;return ;}for(int i p; i n; i)dfs(cnt1, suma[i], i1); //继续选下一个并且下一个在a[i]后面return ;
}
int main(){cin n k;for(int i0; in; i) cin a[i];dfs(0, 0, 0);cout ans;return 0;
}java代码
import java.util.Scanner;
public class Main {static int n, k;static int[] a;static int ans;public static void main(String[] args) {Scanner sc new Scanner(System.in);n sc.nextInt();k sc.nextInt();a new int[n];for (int i 0; i n; i) a[i] sc.nextInt(); dfs(0, 0, 0);System.out.println(ans);sc.close();}static boolean isPrime(int s) {if (s 1) return false;for (int i 2; i Math.sqrt(s); i) if (s % i 0) return false; return true;}static void dfs(int cnt, int sum, int p) {if (cnt k) {if (isPrime(sum)) ans;return;}for (int i p; i n; i) dfs(cnt 1, sum a[i], i 1); }
}python代码
n, k map(int, input().split())
a list(map(int, input().split()))
ans 0
def is_prime(s):if s 1: return Falsefor i in range(2, int(s ** 0.5) 1):if s % i 0: return Falsereturn True
def dfs(cnt, sum, p):global ansif cnt k:if is_prime(sum): ans 1returnfor i in range(p, n):dfs(cnt 1, sum a[i], i 1)
dfs(0, 0, 0)
print(ans)3.2 素数筛 素数筛用来解决这个问题给定正整数n求2~n内所有的素数。 可以用上一节的素数判定方法一个个地判断计算复杂度是O()。这个计算量有点大有没有更快的方法 容易想到用“筛子”把非素数筛掉剩下的就是素数。例如用2去筛2~n内的数一次可以把所有的偶数筛掉。 有两种素数筛埃氏筛、欧拉筛。埃氏筛的计算复杂度是O(nloglogn)欧拉筛的复杂度是O(n)不可能更快了。埃氏筛的编码简单一般情况下也够用。 埃氏筛的操作很简单。下面以初始数列{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}为例说明它的操作步骤。 1记录最小的素数2然后筛掉2的倍数得{2, 3, 4 , 5, 6 , 7, 8 , 9, 10 , 11, 12 , 13}。 2记录下一个素数3然后筛掉3的倍数得{2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13}。 3记录下一个素数5然后筛掉5的倍数得{2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13}。 继续以上步骤直到结束。 下面是代码其中visit[i]记录数i的状态如果visit[i] true表示它被筛掉了不是素数。用prime[]存放素数例如prime[1]2是第一个素数。 C代码
const int N 1e7; //定义空间大小1e7约10M
int prime[N1]; //存放素数它记录visit[i] false的项
bool visit[N1]; //visit[i] true表示i被筛掉不是素数
int E_sieve(int n) { //埃氏筛法计算[2, n]内的素数int k0; //统计素数个数for(int i0; in; i) visit[i] false; //初始化for(int i2; in; i) { //从第一个素数2开始。可优化1if(!visit[i]) {prime[k] i; //i是素数存储到prime[]中for(int j2*i; jn; ji) //i的倍数都不是素数。可优化2visit[j] true; //标记为非素数筛掉}}return k; //返回素数个数
}java代码
public class Main {public static int N 10000000; // 定义空间大小1e7约10M
public static int[] prime new int[N 1];
// 存放素数它记录visit[i] false的项
public static boolean[] visit new boolean[N 1];
// visit[i] true表示i被筛掉不是素数public static int E_sieve(int n) { // 埃氏筛法计算[2, n]内的素数int k 0; // 统计素数个数for (int i 0; i n; i) visit[i] false; // 初始化for (int i 2; i n; i) { // 从第一个素数2开始。可优化1if (!visit[i]) {prime[k] i; // i是素数存储到prime[]中for (int j 2*i; jn; ji) //i的倍数都不是素数。优化2visit[j] true; // 标记为非素数筛掉}}return k; // 返回素数个数}public static void main(String[] args) {int n 100;int primeCount E_sieve(n);System.out.println(cnt of prime: primeCount);System.out.print(list of prime:);for (int i 1; i primeCount; i)
System.out.print(prime[i] ); }
}python代码
N 10000000 # 定义空间大小1e7约10M
prime [0] * (N 1) # 存放素数它记录visit[i] false的项
visit [False] * (N 1) # visit[i] True表示i被筛掉不是素数
def E_sieve(n):k 0 # 统计素数个数visit[0: n 1] [False] * (n 1) # 初始化for i in range(2, n 1): # 从第一个素数2开始。可优化1if not visit[i]:k 1prime[k] i # i是素数存储到prime[]中for j in range(2*i, n1, i): # i的倍数都不是素数。可优化2visit[j] True # 标记为非素数筛掉return k # 返回素数个数
n 100
primeCount E_sieve(n)
print(cnt of prime, primeCount)
print(list of prime, end)
for i in range(1, primeCount 1): print(prime[i], end )上述代码有2处可以优化 1用来做筛除的数2、3、5…等最多到就 n \sqrt{n} n 可以了。例如求n 100以内的素数用2、3、5、7筛就足够了。其原理和试除法一样非素数k必定可以被一个小于等于 k \sqrt{k} k 的素数整除被筛掉。这个优化很大。 2for(int j2*i; jn; ji) 中的j 2*i优化为 j i*i。例如i 5时2*5、3*5、4*5已经在前面i 2, 3, 4的时候筛过了。这个优化较小。 下面给出优化后的代码。 C代码
int E_sieve(int n) {for(int i 0; i n; i) visit[i] false;for(int i 2; isqrt(n); i) //筛掉非素数 if(!visit[i])for(int ji*i; jn; ji) visit[j] true; //标记为非素数
//下面记录素数int k0; //统计素数个数for(int i 2; i n; i)if(!visit[i]) prime[k] i; //存素数prime[1]2, prime[2]3...return k; //返回素数个数
}java代码
public class Main {public static int N 10000000; // 定义空间大小1e7约10M
public static int[] prime new int[N 1];
// 存放素数它记录visit[i] false的项
public static boolean[] visit new boolean[N 1];
// visit[i] true表示i被筛掉不是素数public static int E_sieve(int n) {for (int i 0; i n; i) visit[i] false;for (int i 2; i Math.sqrt(n); i) // 筛掉非素数if (!visit[i]) for (int j i * i; j n; j i)visit[j] true; // 标记为非素数 // 下面记录素数int k 0; // 统计素数个数for (int i 2; i n; i) if (!visit[i]) prime[k] i; // 存素数prime[1]2, prime[2]3... return k; // 返回素数个数}public static void main(String[] args) {int n 100;int primeCount E_sieve(n);System.out.println(cnt of prime: primeCount);System.out.print(list of prime:);for (int i 1; i primeCount; i) System.out.print(prime[i] ); }
}python代码
import math
N 10000000 # 定义空间大小1e7约10M
prime [0] * (N 1) # 存放素数它记录visit[i] false的项
visit [False] * (N 1) # visit[i] True表示i被筛掉不是素数
def E_sieve(n):for i in range(n 1): visit[i] Falsefor i in range(2, int(math.sqrt(n)) 1): # 筛掉非素数if not visit[i]:for j in range(i * i, n 1, i):visit[j] True # 标记为非素数# 下面记录素数k 0 # 统计素数个数for i in range(2, n 1):if not visit[i]:k 1prime[k] i # 存素数prime[1]2, prime[2]3...return k # 返回素数个数
n 100
primeCount E_sieve(n)
print(cnt of prime:, primeCount)
print(list of prime, end)
for i in range(1, primeCount 1): print(prime[i], end ) 埃氏筛的计算复杂度2的倍数被筛掉计算n/2次3的倍数被筛掉计算n/3次5的倍数被筛掉n/5次…总计算量等于n/2n/3n/5n/7n/11…约为O(nloglogn)。计算量很接近线性的O(n)已经相当好了。 空间复杂度代码用到了bool visit[N1]数组当N 1 0 7 10^7 107时约10M。由于埃氏筛只能用于处理约n 1 0 7 10^7 107的问题10M空间是够用的。 埃氏筛可以算出[2, n]内的素数不过更常见的应用场景是计算[L, R]区间内的素数L、R极大但R-L较小此时也可以用埃氏筛。见下面的例题。 素数密度 问题描述给定区间[L,R] (1≤L≤R231R-L≤106)请计算区间中素数的个数。 输入第一行两个正整数L和R。 输出一行一个整数表示区间中素数的个数。 输入样例 2 11 输出样例 5 简单的思路是先分别筛出[2, L]和[2, R]内各有多少个素数然后两者相减就是[L,R]内的素数个数。但是由于L和R最大是 2 31 2^{31} 231用埃氏筛会超时。 由于R-L≤ 1 0 6 10^6 106很小如果只在[L, R]范围内做素数筛计算量很小。如何筛前面提到在[2, n]内做素数筛时只用[2, n \sqrt{n} n ]内的素数去筛就可以了。本题的的n是L、R R \sqrt{R} R 50000所以只需要先计算出50000以内的素数然后用这些素数在[L, R]内筛去合数剩下的就是素数。 还有一个编程问题需要解决。前面的埃氏筛代码用visit[]数组记录被筛的情况若visit[i] true表示数字i被筛去。本题的i 2 31 2^{31} 231如果仍然直接用visit[]数组记录数组大小需要达到 2 31 2^{31} 231 2G空间肯定不够用。解决方案是记录在visit[1]~visit[R-L1]中visit[1]记录L是否被筛visit[2]记录L1是否被筛…visit[R-L1]记录R是否被筛。相关代码见24~27行。 C代码
#includebits/stdc.h
using namespace std;
const int N 1e61;
int prime[50000]; //存放素数p[1]2,p[2]3...
bool vis[N1]; //vis[i]true表示被筛掉i不是素数
int E_sieve(int n) {for(int i 0; i n; i) vis[i] false;for(int i 2; isqrt(n); i)if(!vis[i])for(int ji*i; jn; ji) vis[j] true;int k0;for(int i 2; i n; i)if(!vis[i]) prime[k] i;return k;
}
int main(){int cnt E_sieve(50000); //先筛出50000内的所有素数int L,R; cin L R;if(L1) L2; //特判L1的情况,1不是素数让L从2开始memset(vis,0,sizeof(vis)); //沿用vis注意清空for(int i1;icnt;i){ //用筛出来的素数在[L,R]中再筛一次int p prime[i];long long start; //注意要用long long因为Lp可能超过intif((Lp-1)/p*p 2*p) start (Lp-1)/p*p;//定位到第一个被筛的数else start 2*p;for(long long jstart;jR;jp) //用long long, jp可能超intvis[j-L1]true; //筛掉。和第10行一样}int ans0;for(int i1;iR-L1;i) //R-L1为区间长度,区间内没被标记的数是素数if(!vis[i]) ans;coutans;
}java代码
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static final int N 1000001;public static int[] prime new int[50000];public static boolean[] vis new boolean[N 1];public static int E_sieve(int n) {Arrays.fill(vis, false);for (int i 2; i * i n; i) if (!vis[i]) for (int j i * i; j n; j i) vis[j] true; int k 0;for (int i 2; i n; i) if (!vis[i]) prime[k] i; return k;}public static void main(String[] args) {Scanner sc new Scanner(System.in);int cnt E_sieve(50000);int L sc.nextInt();int R sc.nextInt();if (L 1) L 2; Arrays.fill(vis, false);for (int i 1; i cnt; i) {int p prime[i];long start;if ((L p - 1) / p * p 2 * p) start (L p - 1) / p * p;else start 2 * p; for (long j start; j R; j p) vis[(int)(j - L 1)] true; }int ans 0;for (int i 1; i R - L 1; i) if (!vis[i]) ans; System.out.println(ans);}
}python代码
import math
def E_sieve(n):prime []vis [False] * (n1)for i in range(2, int(math.sqrt(n))1):if not vis[i]:for j in range(i*i, n1, i): vis[j] Truefor i in range(2, n1):if not vis[i]: prime.append(i)return primeif __name__ __main__:prime E_sieve(1000000)cnt len(prime)L, R map(int, input().split())if L 1: L 2vis [False] * (R-L1)for i in range(cnt):p prime[i]if (Lp-1)//p*p 2*p: start (Lp-1)//p*pelse: start 2*pfor j in range(start, R1, p): vis[j-L] Trueans 0for i in range(R-L1):if not vis[i]: ans 1print(ans)3.3 质因数分解 正整数n可以唯一地分解为有限个素数的乘积 n p 1 c 1 p 2 c 2 . . . p m c m n p_1^{c1}p_2^{c2}...p_m^{cm} np1c1p2c2...pmcm其中 c i c_i ci都是正整数 p i p_i pi都是素数且从小到大。 分解质因子的简单方法也是试除法。求n的质因子 1求最小质因子 p 1 p_1 p1。从小到大检查从2到 n \sqrt{n} n 的所有数如果它能整除n就是最小质因子。然后连续用p1除n目的是去掉n中的 p 1 p_1 p1此时n更新为较小的 n 1 n_1 n1。 2再找 n 1 n_1 n1的最小质因子。从小到大检查从 p 1 p_1 p1到的所有数。从 p 1 p_1 p1开始是因为 n 1 n_1 n1没有比 p 1 p_1 p1小的素因子而且 n 1 n_1 n1的因子也是n的因子。 3继续步骤2直到结束。 最后如果剩下一个大于1的数那么它也是一个素数是n的最大质因子。例如6119 29*211找到29后剩下的 n 1 n_1 n1211由于29≥ 211 \sqrt{211} 211 无法执行上面步骤2说明211无法继续分解它是一个素数也是质因子。 试除法的复杂度是O( n \sqrt{n} n )效率较低不过一般也够用。 因数分解 问题描述每个正整数都可以分解成素数的乘积例如62×320 2 2 2^2 22×5。现在给定一个正整数请按要求输出它的因数分解式。 输入输入第一行包含一个正整数N。2≤N≤ 1 0 12 10^{12} 1012。 输出输出一行为的因数分解式。要求按质因数由小到大排列乘号用星号*表示且左右各空一格。当且仅当一个素数出现多次时将它们合并为指数形式用上箭头^表示且左右不空格。 输入样例 20 输出样例 2^2 * 5 C代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
int main(){ll n; cinn;for (ll i2;i sqrt(n);i) { //注意n是变化的ll cnt0; // 记录质因数i的个数if (n%i0) { // i是质因数while(n%i0) { //把n中的i除尽n/i; //更新ncnt; }if (cnt1) couti; //如果i只有一个不输出指数else couti^cnt; //输出指数if (n1) cout * ; //如果不是最后一个质因数输出乘号}}if (n1) coutn; //没分解干净输出剩下的质因数return 0;
}java代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);long n sc.nextLong(); for (long i 2; i Math.sqrt(n); i) {int cnt 0;if (n % i 0) {while (n % i 0) {n / i;cnt;}if (cnt 1) System.out.print(i);else System.out.print(i ^ cnt); if (n 1) System.out.print( * ); }} if (n 1) System.out.print(n); sc.close();}
}python代码
import math
n int(input())
for i in range(2, int(math.sqrt(n)) 1):cnt 0if n % i 0:while n % i 0:n // icnt 1if cnt 1: print(i, end)else: print(i, ^, cnt, sep, end)if n 1: print( * , end)
if n 1: print(n)
