超完整素数算法总结归纳

目录

素数的判定

Eratosthenes筛选（素数筛选）

因子数与因子和

 完美数

n的第k个因子

分拆质数和

分解质因数

最接近的因数

 丑数

素数的判定

Eratosthenes筛选（素数筛选）

因子数与因子和

完美数

n的第k个因子

分拆质数和

分解质因数

四因数 

最接近的因数

 丑数

---

素数的判定

素数的概念是只可以被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 个因子

给你两个正整数 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 0

Sample 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("%d\n", 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;
}