质数：在大于1的整数中，如果只包含1和本身这两个约数，则称该数为质数或者素数
（1）判断质数（试除法）
（2）分解质因素（试除法）
（3）求1~n中所有的质数
（4）阶乘分解
1、判断质数（试除法）)
（1）从定义出发判断是否质数
时间复杂度O（n）
static boolean is_primes(int x)
{
if(x < 2) return false;
for(int i = 2;i <= x;i ++)
{
if(x % i == 0) return false;
}
return true;
}
（2）从整除角度出发判断是否质数
定理：n中最多只包含一个大于的质数
时间复杂度
若d能整除n，则d/n 也能整除n，例如 2能整除12 ，则6也能整除12
从小到大枚举到 min（d,n/d）,不妨设d <= n/d,则d^2 <= n
static boolean is_primes(int x)
{
if(x < 2) return false;
for(int i = 2;i <= x / i;i ++)
{
if(x % i == 0) return false;
}
return true;
}
2、分解质因素（试除法）
public static void divide(int x)
{
for(int i = 2;i <= x / i;i++)
{
if(x % i == 0)
{
int s = 0;
while(x % i == 0)
{
s ++;
x /= i;
}
System.out.println(i + " " + s);
}
}
if(x > 1) System.out.println(x + " " + 1);
System.out.println();
}
3、求1~n中所有的质数
（1）朴素筛法
原理：任意整数x的倍数2x,3x,...都不是质数
由于每次筛选的个数的累加是
(n/2 + n/3 + n/4 +... + n/n) = n(1 + 1/2 + 1/3 +...+ 1/n) = nlnn
static int N = 1000000;
static int[] primes = new int[N];
static boolean[] st = new boolean[N];
static int cnt = 0;//记录质数的个数
public static void get_primes(int n)
{
for(int i = 2;i <= n;i++)
{
if(!st[i])
{
primes[cnt ++] = i;
}
for(int j = i * 2;j <= n;j += i)
st[j] = true;
}
}
（2）埃氏筛法
只需把质数的倍数筛掉即可
从1到n中一共有n/(lnn)个质数
每次筛选的个数的累加是
(n/2 + n/3 + n/5 + n/7 + n/11 +...+ 1/n) =
static int N = 1000000;
static int[] primes = new int[N];
static boolean[] st = new boolean[N];
static int cnt = 0;//记录质数的个数
public static void get_primes(int n)
{
for(int i = 2;i <= n;i++)
{
if(!st[i])
{
primes[cnt ++] = i;
for(int j = i * 2;j <= n;j += i)
st[j] = true;
}
}
}
（2）线性筛法
原理：每个合数i * p只会被它的最小质因子p筛一次
1、i % primes[j] == 0
primes[j]一定是i的最小质因子，primes[j]一定是primes[j] * i的最小质因数
2、i % primes[j] != 0
primes[j] 一定小于i的所有质因子，primes[j]一定是primes[j] * i的最小质因数
注意：在 2 操作中，若满足则必须停下，否则j ++ 时，后面的i * primes[j] 的最小质因子不是primes[j]
注意：筛[0,n]区间内的质数和筛[0,n)区间内的质数的区别在于这行代码for (int j = 0; i * primes.get(j) < n; j++) ，若i * primes.get(j) <= n，则就筛[0,n]的所有质数,也可以写成primes.get(j) <= n / i;i * primes.get(j) < n，则筛[0,n]的所有质数
static int N = 1000010;
static boolean[] st = new boolean[N];//st[x]存储x是否被筛掉
static int cnt = 0;
static int[] primes = new int[N];//primes[]存储所有素数
public static void get_primes(int x)
{
for(int i = 2;i <= x ;i++)
{
if(!st[i]) primes[cnt ++] = i;
for(int j = 0;primes[j] <= x / i;j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;//primes[j]一定是i的最小质因子
}
}
}
4、阶乘分解
算法分析
- 1、筛出1~10^6的所有质数
- 2、枚举每个质因子
P，n!表示1 * 2 * 3... * n,从1到n中，求P的次数：(一共有
项)
-
P的倍数有个
-
P^2的倍数有个
-
P^3的倍数有个
- ...
-
时间复杂度 )
有个质数，每个质数求
次，因此时间复杂度是
级别
Java 代码
import java.util.Scanner;
public class Main {
static int N = 1000010;
static boolean[] st = new boolean[N];
static int[] primes = new int[N];
static int cnt = 0;
static void init(int n)
{
for(int i = 2;i <= n;i ++)
{
if(!st[i]) primes[cnt ++] = i;
for(int j = 0;primes[j] * i <= n;j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
init(n);
for(int i = 0;i < cnt;i ++)
{
int p = primes[i],s = 0;
for(int j = n;j != 0;j /= p)
{
s += j / p;
}
System.out.println(p + " " + s);
}
}
}
快速幂
&是二进制的“与”运算
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 0
3 & 2 = 0111 & 0010 = 0010 = 2
x & 1 的结果就是取二进制的最末位
x & 1 == 0 , 则 x 为偶数
x & 1 == 1 , 则 x 为奇数
>> 运算比较单纯，二进制去掉最后一位
public static long qmi(int a,int k,int p)
{
long res = 1 % p;
long t = a;
while(k > 0)
{
if((k & 1) == 1) res = res * t % p;
k >>= 1;
t = t * t % p;
}
return res;
}
快速幂求逆元
引理：
证明分析：
费马小定理的推导来自杨辉三角形，在杨辉三角形中，可以发现每一行都是
n为任意质数p时，因为在展开过程中没有被约分过，因此展开式中的系数除了第一项和最后一项，其余全是p的倍数，因此当
p为质数时，由于下列方程一定成立
由于第二大项一定是质数p的倍数，对于这个式子的某个命题，第n项成立，则第
当
由数学归纳法，费马小定理证毕。
给定n组ai,pi，其中pi是质数,求ai模pi的乘法逆元，若逆元不存在则输出impossible。
import java.util.Scanner;
public class Main {
public static long qmi(int a,int k,int p)
{
long res = 1 % p;
long t = a;
while(k > 0)
{
if((k & 1) == 1) res = res * t % p;
k >>= 1;
t = t * t % p;
}
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
while(n -- > 0)
{
int a = scan.nextInt();
int p = scan.nextInt();
long t = qmi(a,p - 2,p);
if(a % p == 0) System.out.println("impossible");//若a是p的倍数，则一定无解
else System.out.println(t);
}
}
}
龟速乘法
算法分析
快速幂与龟速乘法的对比
快速幂解决
的问题，而龟速乘法解决
的问题
本质上
快速幂：
龟速乘：
快速幂：从 算出
, 再算出
，
...(通过
的二进制中哪些位需要加上该位的值，算出
)
龟速乘：从 算出
, 再算出
，
...(通过
的二进制中哪些位需要加上该位的值，算出
)
注意:Java 的同学还可以直接使用BigInteger算很大的值
时间复杂度 )
参考文献
算法提高课
Java 代码(龟速乘)
import java.util.Scanner;
public class Main {
static long qadd(long a,long k,long p)
{
long res = 0;
while(k > 0)
{
if((k & 1) == 1) res = (res + a) % p;
k >>= 1;
a = (a + a) % p;
}
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
long a = scan.nextLong();
long b = scan.nextLong();
long p = scan.nextLong();
System.out.println(qadd(a,b,p));
}
}
Java 代码(BigInteger)
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
BigInteger a = new BigInteger(scan.next());
BigInteger b = new BigInteger(scan.next());
BigInteger p = new BigInteger(scan.next());
System.out.println(a.multiply(b).mod(p));
}
}
扩展欧几里得
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int x;
static int y;
public static int exgcd(int a,int b,int[] x,int[] y)
{
if(b == 0)
{
x[0] = 1;
y[0] = 0;
return a;
}
int d = exgcd(b,a % b,y,x);
y[0] = y[0] - a/b * x[0];
return d;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine().trim());
int[] x = new int[1];
int[] y = new int[1];
while(n -- > 0)
{
String[] s1 = reader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
exgcd(a,b,x,y);
System.out.println(x[0] + " " + y[0]);
}
}
}
