1 求素树
1 求解素树我们是利用筛法:对于不超过MAXN的每个整数x,我们只要去删除2x,3x,4x......,当处理完MAXN个数之后剩下的即为素数
2 时间复杂度分析:外层为O(n),内层总的次数为小于n/2+n/3+n/4+......+n/n,那么总的O(nlogn)
2 求因子个数
1 对于最大的值来说,我们只要枚举到sqrt(MAXN),然后我们对于每个i,去枚举j从(i+1, j*i<MAXN) , 这样我们求出
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e6;
int prime[MAXN];
int divide[MAXN];
// 求素树
void getPrime(){
bool vis[MAXN];
int pos = 0;
memset(vis , false , sizeof(vis));
for(int i = 2 ; i < MAXN ; i++){
if(!vis[i])
prime[pos++] = i;
for(int j = i*2 ; j < MAXN ; j += i)
vis[j] = true;
}
}
// 求因子的个数
void getDivide(){
int t = sqrt(MAXN*1.0);
for(int i = 1 ; i <= t ; i++){
for(int j = i+1 ; j*i < MAXN ; j++)
divide[i*j] += 2; //i和j是不同的,因此加2 divide[i*i]++; //i和i相同那么加1即可
}
}
int main(){
getPrime();
getDivide();
return 0;
}
分享到:
相关推荐
【算法1-1-2】唯一的缺点是在计算各个质因子的个数的过程中无法同时生成质数表,因此质数表需要事先提供或另行计算。从这个例子中可以看到,在相同的数据结构上可以采用不同的算法,并产生不同的效果。 有时,算法的...
8.12输入10个学生5门课的成绩,分别用函数求:(1)每个学生的平均分;(2)每门课的平均分;(3)找出最高的分数所对应的学生和课程;(4)求出平均分方差; 57 8.13写几个函数:(1)输入10个职工的姓名和职工号;...
1.程序分析:利用for循环控制100-999个数,每个数分解出个位,十位,百位。 【程序4】 题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。 程序分析:对n进行分解质因数,应先找到一个最小的质数k,...
1.输出所有的“水仙花数...23.有5个同学,每个同学有三门课成绩,从键盘输入学号,姓名和三门课的成绩,取平均数,将数据存放在磁盘文件stud中; 24.如果一个数恰好等于它的因子之和,则叫“完数”求1000以内所有完数;
1.6 调用函数f,输出n的所有质数因子 1.7 改方法返回个位数为6,并且能被3整除的4位数的个数 1.8 对x=1,2,….,10,求f(x)=x*x-5*x+sin(x)的最大值 1.9 被3除余数为1,被5除余数为3,被7除余数为5 统计满足条件x*x+y*...
(2)编写一个程序实现如下功能:输入10个学生5门课程的成绩,分别用函数求:①每个学生的平均分;②每门课程的平均分;③找出最高的分数所对应的学生和课程。 若输入2个学生的成绩,其运行结果如下图所示。 (3...
1.程序分析:利用for循环控制100-999个数,每个数分解出个位,十位,百位。 【程序4】 题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。 程序分析:对n进行分解质因数,应先找到一个最小的质数k...
题目:一个数如果恰好等于它的因子之和,这个数就称为“完数”。例如6=1+2+3.编程 找出1000以内的所有完数。 【程序19】 题目:一球从100米高度自由落下,每次落地后反跳回原高度的一半;再落下,求它在 第10...
题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? //这是一个菲波拉契数列问题 public class lianxi01 { ...
1.程序分析:利用for循环控制100-999个数,每个数分解出个位,十位,百位。 2.程序源代码: #include "stdio.h" #include "conio.h" main() { int i,j,k,n; printf("'water flower'number is:"); for(n=100;n;n++...
全书共提供300个实例,每个实例都突出了其实用性。 本书既可作为C程序的初学者学习用书,也可作为程序开发人员、相关培训机构老师和学生的参考用书。 第1章 基础知识 1 1.1 进制转换 2 实例001 十进制转换为...
综合(课程设计) 内容及步骤: 1、假定一维数组a[n]中的每个元素值均在[0,200]区间内,用C++编写一个算法,分别统计出落在[0,20],[21,50],[51,80],[81,130],[131,200]等各区间内的元素个数。...