文档章节

复试训练——数学问题—— 分解素因数

wudangt
 wudangt
发布于 2017/02/02 18:30
字数 594
阅读 4
收藏 0

题目1207:质因数的个数

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:7733

解决:2510

题目描述:

求正整数N(N>1)的质因数的个数。

相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。

输入:

可能有多组测试数据,每组测试数据的输入是一个正整数N,(1<N<10^9)。

输出:

对于每组数据,输出N的质因数的个数。

样例输入:

120

样例输出:

5

提示:

注意:1不是N的质因数;若N为质数,N是N的质因数。

来源:

2007年清华大学计算机研究生机试真题

代码:

#include <stdio.h>
#include <string.h>
bool mark[100001];
int prime[100001];
int primeSize;
void init(){
	int i;
	for(i=2;i<=1000000;i++){
		mark[i]=false;
	}
	primeSize=0;
	for(i=2;i<=1000000;i++){
		if(mark[i]==true) continue;
		mark[i]=false;
		int j;
		prime[primeSize++]=i;
		for(j=i*i;j<=1000;j+=i){
			mark[j]=true;
		}

	}

}
int main(){
	init();
	int n;
	while(scanf("%d",&n)!=EOF){
		int ansPrime[30];
		int ansSize=0;
		int ansNum[30];
		int i;
		for(i=0;i<primeSize;i++){
			if(n%prime[i]==0){
				ansPrime[ansSize]=prime[i];
				ansNum[ansSize]=0;
				while(n%prime[i]==0){
					ansNum[ansSize]++;
					n/=prime[i];
				}
				ansSize++;
				if(n==1) break;
			}
		}
		if(n!=1){
			ansPrime[ansSize]=n;
			ansNum[ansSize]=1;
		}
		int ans=0;
		for(i=0;i<ansSize;i++){
			ans+=ansNum[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}

题目1104:整除问题

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:5331

解决:1789

题目描述:

给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。

输入:

两个整数n(2<=n<=1000),a(2<=a<=1000)

输出:

一个整数.

样例输入:

6 10

样例输出:

1

来源:

2011年上海交通大学计算机研究生机试真题

代码:

#include <stdio.h>
#include <string.h>
bool mark[1010];
int prime[1010];
int primeSize;
void init(){
	int i;
	for(i=1;i<=1000;i++){
		mark[i]=false;
	}
	primeSize=0;
	for(i=2;i<=1000;i++){
		if(mark[i]==true) continue;
		mark[i]=false;
		prime[primeSize++]=i;
		int j;
		for(j=i*i;j<=1000;j+=i){
			mark[j]=true;
		}
	}
}

int cnt[1010];
int cnt2[1010];
int main(){
	int n,a;
	init();
	while(scanf("%d%d",&n,&a)!=EOF){
		int i;
		for(i=0;i<primeSize;i++)
			cnt[i]=cnt2[i]=0;		
		for(i=0;i<primeSize;i++){
			int t=n;
			while(t){
				cnt[i]+=t/prime[i];
				t=t/prime[i];
			}
		}		
		int ans=123123123;
		for(i=0;i<primeSize;i++){
			while(a%prime[i]==0){
			cnt2[i]++;
			a/=prime[i];
			}
			if(cnt2[i]==0) continue;
			if(cnt[i]/cnt2[i]<ans){
			  ans=cnt[i]/cnt2[i];
			}

		}
		printf("%d\n",ans);
	}
	return 0;
}

 

© 著作权归作者所有

wudangt
粉丝 0
博文 46
码字总数 23847
作品 0
黄浦
其他
私信 提问
原创开源 VB 小程序: 质数判断(因数分解)

原创开源 VB 小程序: 质数判断(因数分解) 闪星空间2014-09-07332 阅读 判断开源vb质数 2014-9-7 P.S.更新 v3.5 版。(本文原发布日期为8月3日) 这是一个判断一正整数(1 除外)是否为质数的...

闪星空间
2014/09/07
0
0
量子计算将能分解任意极大整数,RSA加密或成摆设

就算是一台超级计算机有可能在数年的时间内计算出任意质因数,这也是得不偿失的。为了科学地解决这个问题,麻省理工学院(MIT)的科学家找到了明确的方法。今天,《科学》杂志最新发表的一篇...

雪花又一年
2018/05/15
0
0
整数的故事(3)——最小公倍数与哥德巴赫猜想

最小公倍数   就像硬币的正反两面,最大公约数往往是和最小公倍数成对出现的。对于两个不等于零的整数a和b,如果a|k且b|k,那么k就是a和b的公倍数;在所有的k中,大于0的最小者就是a和b的最...

我是8位的
01/14
0
0
砝码分盐问题——从数学和计算机的角度分析(7)

本博客(http://blog.csdn.net/livelylittlefish)贴出作者(阿波)相关研究、学习内容所做的笔记,欢迎广大朋友指正! Content 0.问题 1.一些方法 2.从数学的角度分析 3.能否编程计算? 4....

晨曦之光
2012/03/09
115
0
Java并发编程学习笔记(一)线程安全性 1

什么是线程安全性: 要编写线程安全的代码,其核心在于要对状态访问操作进行管理,特别是对共享的和可变的状态的访问。“共享”意味着变量可以由多个线程同时访问,而“可变”则意味着变量的...

ponpon_
2014/05/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部