UVa 294 - Divisors 解题报告 c语言实现 素数筛法
2024-10-19 03:39:45
1.题目大意:
输入两个整数L、H其中($1≤L≤H≤10^9,H−L≤10000$),统计[L,H]区间上正约数最多的那个数P(如有多个,取最小值)以及P的正约数的个数D。
2.原理:
对于任意的一个正整数N,若有$N=p_1^{e1}p^{e2}_2...p^{er}_r$ 且$p_1、p_2...p_r$都为素数,则有N的因数个数为$(e1+1)(e2+1)...(er+1)$。
3.范围确定
关于对maxn的确定,由$1≤L≤H≤10^9$可知:对 $10^9$ 开根号,大概估算一下,将maxn取32000。
4.思路
考虑先素数筛法打表得出32000以内所有素数,然后把因数个数求出来,若大于之前出现过的最大因子数,则修改;反之,不变。
5.代码:
#include"stdio.h"
#define maxn 32000
int prime[maxn],origin[maxn]; int getfactor(int* prime ,int i)// 求出因数个数
{
int sum=1,count;
for(int j=1; j<prime[0]&&i!=1; j++)
if(i%prime[j]==0)
{
count=1;
while(i%prime[j]==0)
{
count++;
i/=prime[j];
}
sum*=count;
}
return sum;
} int main()
{
/* 利用素数筛法得出32000以内所有素数 存入prime数组中 */
for(int i=0; i<maxn; i++)
origin[i]=1;
for(int i=2; i<maxn; i++)
if(origin[i])
for(int j=2*i; j<maxn; j+=i)
origin[j]=0;
prime[0]=0;
for(int i=2; i<maxn; i++)
if(origin[i])
prime[++prime[0]]=i; // 用prime[0]表示素数个数 /* 利用getfactor函数得出因子数 ,
若大于之前出现过的最大因子数,则存入d. */
int t,n,l,h,p,d;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&l,&h);
d=0;
for(int i=l; i<=h; i++)
{
n=getfactor(prime,i);
if(n>d)
{
d=n;
p=i;
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.\n",l,h,p,d);
}
return 0;
}
最新文章
- 微信官方开源UI库-WeUI
- JS子父窗口互相操作取值赋值的方法介绍
- Android上滑手势触发和不增加布局层级扩大点击区域
- C#执行XSL转换
- puppet 安装
- 《剑指offer-名企面试官精讲典型编程题》读后感
- hdu 1352 I Conduit!
- 孟岩的c++ 的学习方法,这何尝有不是做人做事的方法呢?
- 正确处理Windows电源事件
- php app版本升级的思路
- Dede 删除文档同时文章中的图片的方法
- 小技巧-WEB API第一次加载很慢
- PS 图像调整算法——饱和度调整
- Mac Launchpad出现两个相同快捷方式的解决办法
- Django学习之十: staticfile 静态文件
- 【jQuery:遍历同样class的全部值,遍历某一列td的值】
- pyspider操作千万级库,pyspider在对接量级较大库的策略
- 《Netty权威指南》目录
- shell 下执行mysql 命令
- Vue--- 手动禁止ESlint