求小于等于n且与n互质的数的个数
互质穷举法
- 互质:两个数互质代表两者最大公约数为1
- 最大公约数求法:辗转相除法,最小公倍数:较大值除以最大公约数乘以较小值
- 辗转相除法:
- 较大的数a取模较小的数b,得取模值c
- 若取模值等于0 则最大公约数为取模值,否则继续下一步
- a与c再次取模,回到第二步
//求最大公约数gcd以及最大公倍数lcm // 36 24 36/24 // 24 12 24/12 // 0 结束最大公约数为12 // 求最小公倍数 // lcma,b = a∗b/gcda,b public static int gcdinta,intb{ //a>=b //辗转相除法 if b==0{ return a; } return gcdb,a; }
- 穷举到n,一一判断该数与n的最大公约数是否为1,即是否为互质
结论:可以实现,但时间复杂度太高
采取欧拉函数进行求取
在数论,对正整数n,欧拉函数是小于等于n的正整数中与n互质的数的数目.
n为正整数n,p1、p2 ……pn 为正整数n的质因数
n的质因数:既是n的因数,又是质数的数
计算方法:
$$
\phi (n) = n \times (\frac{p_1-1}{p_1})\times (\frac{p_2-1}{p_2})\cdots\times (\frac{p_n-1}{p_n})
$$
例:
$$
\phi (10) = 10 \times \frac{1}{2}\times \frac{4}{5} = 4
$$
-
质数的求法:因数只有1和其本身
-
单个质数n的判断
依次判断2到$ \sqrt{n} $的数被n取模的值是否等于零,存在任意一个即不为质数
当p大于$\sqrt{n}$时,代表数p一定可以得到一个小于!$\sqrt{n}$的数和一个大于$\sqrt{n}$的成对因数,不为质数
-
从2到n的质数的判断
非穷举,穷举时间复杂度为O(n),使用素数筛法为O($\log_{}{n}$)
{card-list}
{card-list-item}
为保证效率,质数为false,合数为true
{/card-list-item}
{card-list-item}
标记2到n的数都为质数,为false,布尔数组默认值为false,无需再一一标记
{/card-list-item}
{card-list-item}
从2开始标记数,找到第一个为false的数p
{/card-list-item}
{card-list-item}
标记数p的倍数为合数,即为true,倍数标记从 $p \times p$ 开始,直至数p等于$ \sqrt{n} $,结束标记
{/card-list-item}
{card-list-item}
使得下一个数p 为未被标记为合数的数,即数值仍为false的数,重复第三步
{/card-list-item}
{card-list-item}
将标记为false 的,即为质数的全部输出
{/card-list-item}
{/card-list}
原因:
p的倍数的因数必有p,不符合质数条件,每次从 $p \times p$ 开始标记是由于$p-p$的部分已经进行了标记,不再重复标记
-
-
采取素数筛法求取质数时,可将倍数标记的操作修改为乘以(1-1/p),使得每一个数都能乘以其质因数
- 依次存入数组中,最后统一依次输出结果。
public static int f1(int n){
int res = n;
for (int i = 2;i*i<=n;i++){
if (n % i==0){
res = res / i*(i-1);//res/i
while (n % i == 0){
n/=i;
}
}
}
if (n>1){
res = res/n*(n-1);
}
return res;
}
//区间内欧拉函数取值
public static int[] f2(int n){
int[] count = new int[n+1];
for (int i = 1;i <= n;i++){
count[i]=i;
}
for (int i =2 ;i <= n;i++){
if (count[i] == i){
for (int j = i;j <= n;j+=i){
count[j] = count[j]/i*(i-1);
}
}
}
return count;
}
知识点:
-
最大公约数、最小公倍数
-
单一质数判断
-
质数筛法:埃氏筛法
-
欧拉函数