超完整素数算法总结归纳Eratosthenes筛选（素数筛选）
目录
素数的判定
素数的概念是只可以被1和他本身可以整除
所以我们可以使用试除法，如一个数为n
（用2-n-1）对n进行试除,但是这样的话时间复杂度是O(N)
#include<stdio.h>
int main()
{
int n=10;
int flag=1;
for(i=2;i<n;i++)
{
if(n%i==0)
{
flag=0;
break;
}
}
if(flag=1)
{
printf("是");
}
else
printf("否");
}这样的时间复杂度还不够优化，我们要知道一点如果说一个数是合数的话，那么他的因数一定是小于等于根号n的，如16，因数有4*4，2*8，其因数一定是在根号n的两边的
所以我们只要对根号n进行试除就可以了，那么时间复杂度就被我们优化到O(sqrt(n))，效率就大大提升了
同时注意一点
1.如果我们用如果用sqrt（n）的话，可能会造成会精度丢失，如n=15，那么开根号出来就不会是一个整数，造成精度丢失
要用的话要加个1e-8，且如果要用到话每次，在循环都要对sqrt进行计算，造成不必要的负担，最好在最前面n=sqrt(N+1e-8),进行替换2.如果我们想用i*i<=n进行计算的话，假如说i的数很大了，那么他们相乘就很有可能会溢出
，如果想用的话，就最好（long long）i*i,对其进行强制类型转化，尽量不让其溢出
3.因此我们的最有解是i<=n/i,这样即保证了时间复杂度，又保证了两边都不会溢出
#include<stdio.h>
int main()
{
int n=10;
int flag=1;
for(i=2;i<=n/i;i++)
{
if(n%i==0)
{
flag=0;
break;
}
}
if(flag=1)
{
printf("是");
}
else
printf("否");
}Eratosthenes筛选（素数筛选）
我们用一个标记数组f[maxi]，其中f[i]=0为素数，否则为非素数，首先我们知道1，和0都不是素数，所以f[0]=1,f[1]=1
1.随后我们在未标记的数里面找最小的数，为2，他不是任何数的的倍数，所以2是素数，此时我们就把所有2的倍数都标记为0；3，6，8，10……2*i
2.我们再从剩余未标记的数里面找最小的数，为3，他也不是任何数的倍数，所以3是素数，此时我们把所有3的倍数也都标记为0；6，9，12，15，18……3*i
3.我们再从所有未标记的数里面找最小的数，为5，他也不是任何数的素数，所以5是素数，此时我们把所有5的倍数都标记为0；10，15，20，25……5*i,
…………以此类推
如果我们要赛选素数的话可以用i<=n/i
如果我们要记录所有的素数的话就用i<n,因为用i<=n/i的话，另外一半的因数就无法被记录进去
同时在内层循环的话，我们用i*i，避免对已经标记过的数，重复标记，浪费时间
如果用2*i,开始的话，如2为素数，那么我们对4，6，8，10…………都已经标记了
到3的时候又对6 9…………进行标记，6我们已经标记过了，
而如果为i*i开始的话，3的时候就是9开始,直接跳过已经标记过的数
因子数与因子和
我们当找到了1到根号n间的因子的时候，即当i 是因子的时候，同时n/i也为他的因子，如果要记录他所有不同的因子，我们只要规定i！=n/i即可，即i*i！=n，
因子和就是所有的找到的所有的因子数相加
#include<stdio.h>
int main()
{
int n=15;
int cnt=0,sum=0;//sum是用来记录所有的因子和，cnt是用来记录有多少个不同的因子
for(i=1;i<=n/i;i++)
{
if(n%i==0)
{
cnt++;
sum+=i;
if(i*i!=n)//避免同一个因子重复记录
{
cnt++;
sum+=n/i;
}
}
sum-=n;//这里是因为要把他本身给删掉了，本身不是他的因数
}
}完美数
对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。
给定一个 整数
n， 如果是完美数，返回true，否则返回false示例 1：
输入：num = 28 输出：true 解释：28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, 和 14 是 28 的所有正因子。示例 2：
输入：num = 6 输出：true示例 3：
输入：num = 496 输出：true示例 4：
输入：num = 8128 输出：true示例 5：
输入：num = 2 输出：false
bool checkPerfectNumber(int num){
int i=1;
int sum=0;
for(i=1;i*i<=num;i++)//如果是i的话会超出去,控制在一半的范围
{
if(num%i==0)
{
sum+=i;//找sqrt内
if(num%(num/i)==0&&num/i!=i)
{
sum+=num/i;
}
}
}
sum-=num;
if(sum==num)
return true;
else
return false;
}n的第k个因子
给你两个正整数
n和k。如果正整数
i满足n % i == 0，那么我们就说正整数i是整数n的因子。考虑整数
n的所有因子，将它们 升序排列 。请你返回第k个因子。如果n的因子数少于k，请你返回 -1 。示例 1：
输入：n = 12, k = 3 输出：3 解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。示例 2：
输入：n = 7, k = 2 输出：7 解释：因子列表包括 [1, 7] ，第 2 个因子是 7 。示例 3：
输入：n = 4, k = 4 输出：-1 解释：因子列表包括 [1, 2, 4] ，只有 3 个因子，所以我们应该返回 -1 。示例 4：
输入：n = 1, k = 1 输出：1 解释：因子列表包括 [1] ，第 1 个因子为 1 。示例 5：
输入：n = 1000, k = 3 输出：4 解释：因子列表包括 [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000] 。提示：
1 <= k <= n <= 1000
int compare(const void*e1,const void *e2)
{
return (*(int*)e1-*(int *)e2);
}
int kthFactor(int n, int k){
int count=0;
int i,j=0;
int arr[1000];
if(n==1&&k==1)
return 1;
for(i=1;i*i<=n;i++)
{
if(n%i==0)
{
arr[j++]=i;
if(i*i!=n)//去重复因子
{
arr[j++]=n/i;
}
}
}
//把所有因子都找出来了
//进行排序
qsort(arr,j,sizeof(int),compare);
if(j<k)//如果实际的因子数小于需要搜索的数，就返回一个-1
return -1;
else
{
return arr[k-1];
}
}分拆质数和
Problem Description
把一个偶数拆成两个不同素数的和，有几种拆法呢？Input
输入包含一些正的偶数，其值不会超过10000，个数不会超过500，若遇0，则结束。Output
对应每个偶数，输出其拆成不同素数的个数，每个结果占一行。Sample Input
30 26 0Sample Output
3 2
思路1.首先先把所有10000内的素数给筛选出来
2.用一个素数数组
3，先枚举素数p,因为两个素数相加可以得到x，所以枚举p在x的一半即可，两者相加只可能在中间值的两边
4.此时再判定k=x-p为质数就自增
#define n 10005
int main()
{
int isprime[10005];
memset(isprime, 0, sizeof(isprime));
int i;
isprime[0] = isprime[1] = 1;
int cnt = 0;
int prime[10005];
int j;
for (i = 2; i <= 10005 ; i++)
{
if (isprime[i] == 0)
{
prime[cnt++] = i;
for (j = i*i; j < 10005; j+=i)
{
isprime[j] = 1;
}
}
}
int x;
while (scanf("%d", &x) && x)//当x为0就停止循环
{
int s = 0;
//先枚举素数p,因为两个素数相加可以得到x，所以枚举p在x的一半即可，两者相加只可能在中间值的两边
for (i = 0; i < cnt&&prime[i] <=(x / 2); i++)
{
int k = x - prime[i];
if (isprime[k] == 0)
{
s++;
}
}
printf("%dn", s);
}
return 0;
}分解质因数
任何一个合数都可以被拆分成所有质数的乘积，
如8=2^2^2, 52=2^2*13,被拆分成了质数的乘积的形式，
所以，如果一个数n可以被2给整除，除完之后n就变成n/2，继续和2除，直到把所有的2，除完，接下来再和3，进行整除，如果可以整除，那么就再把所有的3都除掉，如果下一个质数不能被整除，就跳过
我们也可以提高精度在根号n内筛选质数，最多只会有一个质数大一根号n
如果在根号n内把所有的质数除干净了，这时候，如果n>1,那么n就会是1个大于根号n的质数
int main()
{
int i;
int arr[10000];
for (i = 2; i <= (n / i); i++)
{
while (n%i == 0)//把其中一个质数除干净
{
arr[j++] = i;//把那个质数因子存起来
n/=i;
}
}
if (n > 1)
{
arr[j++] = n;
}
}好了学完了质数相关的知识，我们开始刷题吧
四因数
给你一个整数数组
nums，请你返回该数组中恰有四个因数的这些整数的各因数之和。如果数组中不存在满足题意的整数，则返回
0。示例：
输入：nums = [21,4,7] 输出：32 解释： 21 有 4 个因数：1, 3, 7, 21 4 有 3 个因数：1, 2, 4 7 有 2 个因数：1, 7 答案仅为 21 的所有因数的和。
int sum(int x)//计算因子和的函数
{
int sum=0;
int i=0;
for(i=1;i<=(x/i);i++)
{
if(x%i==0)
{
sum+=i;
if(i*i!=x)
{
sum+=(x/i);
}
}
}
return sum;
}
bool fourfactor(int n)//判断是否有4个因子的函数
{
int i;
int cnt=0;
for(i=1;i<=(n/i);i++)
{
if(n%i==0)
{
cnt++;
if(i*i!=n)
{
cnt++;
}
}
}
if(cnt==4)
return true;
else
return false;
}
int sumFourDivisors(int* nums, int numsSize){
//先对每一个进行拆分是否有4个因数，
//拆分完后如果有4个因子
int i=0;
int addsum=0;
for(i=0;i<numsSize;i++)
{
if(fourfactor(nums[i]))
{
addsum+=sum(nums[i]);//addsum就把因子和加起来
}
}
if(addsum)
{
return addsum;
}
return 0;
}最接近的因数
给你一个整数
num，请你找出同时满足下面全部要求的两个整数：
- 两数乘积等于
num + 1或num + 2- 以绝对差进行度量，两数大小最接近
你可以按任意顺序返回这两个整数。
示例 1：
输入：num = 8 输出：[3,3] 解释：对于 num + 1 = 9，最接近的两个因数是 3 & 3；对于 num + 2 = 10, 最接近的两个因数是 2 & 5，因此返回 3 & 3 。示例 2：
输入：num = 123 输出：[5,25]示例 3：
输入：num = 999 输出：[40,25]提示：
1 <= num <= 10^9
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* closestDivisors(int num, int* returnSize)
{
//分别对n+1，和n+2进行因数分解，两者间的差值最小，比较的是差值的绝对值
int i;
int *ret = (int *)malloc(sizeof(int) * 2);
*returnSize = 2;
int min =-1;
int j;
int x, y;
int flag = 1;
for (i = num + 1; i <= num + 2; i++)
{
for (j = 1; j <= i / j; j++)
{
if (i%j == 0)//j是其中的一个因数，这个时候i/j也是其中一个因数
{
if (min >= abs(j - i / j) || min == -1)//我们初始化m为一个负数，避免对后续产生印象，假如第一次成立的化也能够进入if语句内部
{
min = abs(j - i / j);
x = j;
y = i / j;
if (min == 0)
{
flag = 0;;
}
}
}
}
if (flag == 0)
{
break;
}
}
ret[0] = x;
ret[1] = y;
return ret;
}丑数
给你一个整数
n，请你判断n是否为 丑数 。如果是，返回true；否则，返回false。丑数 就是只包含质因数
2、3和/或5的正整数。示例 1：
输入：n = 6 输出：true 解释：6 = 2 × 3示例 2：
输入：n = 8 输出：true 解释：8 = 2 × 2 × 2示例 3：
输入：n = 14 输出：false 解释：14 不是丑数，因为它包含了另外一个质因数7。
bool isUgly(int n)
{
if(n==1)
{
return true;
}
if(n<=0)
{
return false;
}
//分解质因数
int i;
int j=0;
int str[2000];
for(i=2;i<=n/i;i++)
{
while(n%i==0)
{
str[j++]=i;
n/=i;
}
}
if(n>1)//此时的n一定是个质数,如果被整除的话，就会n=1，所以整个条件控制的是n>1d
str[j++]=n;
int k=0;
int m=0;
for(k=0;k<j;k++)
{
if(str[k]==2||str[k]==3||str[k]==5)
{
m++;//如果他是这3者其中一个质因数，m自增
}
}
if(m==j)//如果m和他的所有质因数相同的时，就是都是这3个质因数
return true;
else
return false;
}