本文主要是介绍SDUTOJ 3115 小鑫找基友 ——素数筛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
小鑫找基友
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
小鑫身上有一个特殊的光环，就是吸引基友的光环。小鑫身上有一个能力值，小鑫能吸引基友的数量为能力值内的质因子的个数。
例如：
小鑫的能力值为12,12 = 2^2*3，那么12包含两个质因子2和3，所以小鑫可以吸引2个基友。
注：在数论里，某一正整数的质因子指能整除该数的质数整数。（源自百度百科）
给定一个能力值n，我们想知道小鑫能够吸引多少的基友。
输入
多组输入。
每组输入，输入一个正整数n(1<=n<=1000 000000)，表示小鑫所拥有的能力值。
输出
计算结果，求出小鑫能够吸引多少基友。
示例输入
12
示例输出
2
提示
来源
GLSilence
示例程序
#include <stdio.h>
#define MAX 100010int pr[MAX] = {2,3,5};
int k = 3;void sss()
{int gad = 2;bool flag;for(int i = 7; i <= MAX; i += gad){flag = false;for(int j = 0; pr[j] * pr[j] <= i; j++){if(i % pr[j] == 0){flag = true;break;}}if(!flag)pr[k++] = i;gad = 6 - gad;}
}
int main()
{sss();int n,sum;while(~scanf("%d",&n)){if(n == 1){printf("0\n");continue;}sum = 0;for(int i = 0; pr[i] <= n && i < k; i++){if(n % pr[i] == 0){sum++;while(n % pr[i] == 0)n /= pr[i];}}if(n != 1)sum++;printf("%d\n",sum);}return 0;
}
这篇关于SDUTOJ 3115 小鑫找基友 ——素数筛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
