目录
素数的判定
Eratosthenes筛选（素数筛选）
因子数与因子和
完美数
n的第k个因子
分拆质数和
分解质因数
最接近的因数
丑数
素数的判定
Eratosthenes筛选（素数筛选）
因子数与因子和
完美数
n的第k个因子
分拆质数和
分解质因数
四因数
最接近的因数
丑数
#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("否"); }
#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("否"); }
#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;//这里是因为要把他本身给删掉了，本身不是他的因数 } }
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个因子
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]; } }
分拆质数和
#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; }
分解质因数
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; } }
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; }
/** * 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; }
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; }
