2 u014206715 u014206715 于 2016.03.04 22:41 提问

分解素因数的问题,输出总是1,跪求各位大神
c

#include
bool mark[100001];
int prime[100001];
int primeSize;
void init(){
primeSize=0;
for(int i=2;i<=100000;i++)
{
if(mark[i]=true)
{
continue;
}
prime[primeSize++]=i;
// if(i>=1000) continue;
for(int j=i*i;j<=100000;j+=i)
{
mark[j]=true;
}
}
}
int main(){
init();
int n;
while(scanf("%d",&n)!=EOF)
{
int ansPrime[30];
int ansNum[30];
int ansSize=0;
for(int 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(int i=0;i<ansSize;i++)
{
ans+=ansNum[i];
}
printf("%d\n",ans);
}
return 0;
}

4个回答

bealing
bealing   Rxr 2016.03.04 23:02

init函数中:
if(mark[i]=true) // mark[i] == true
{
continue;
}

bealing
bealing 至于C语言中静态分配内存的大小的上限是多少,学完《操作系统》你可以自己探索
2 年多之前 回复
bealing
bealing 只改这一个地方是不行的,至少我运行的时候是不行的,因为C语言中静态分配内存的大小是有上限的,mark;prime数组长度太长了,都改为100,基本上就够用,你可以把这两个数组打印出来看看
2 年多之前 回复
u014206715
u014206715 回复Bealing: init函数是没问题的啊,你改完之后运行出来了?
2 年多之前 回复
u013596119
u013596119   Rxr 2016.03.04 23:07

init()这样改

 void init(){
    primeSize=0;
    for(int i=2;i<=100000;i++)
    {
        if(mark[i]==true)
        {
        continue;
        }       
        prime[primeSize++]=i;
// if(i>=1000) continue;
        for(int j=i;j<=100000;j+=i)
        {
            mark[j]=true;
        }
    }
}
u014206715
u014206715 回复DarthHaric: 出来的答案是不正确的吧,输出一直是1
2 年多之前 回复
u013596119
u013596119 回复玉面老飞龙: 运行出来了。。。
2 年多之前 回复
u014206715
u014206715 回复DarthHaric: init函数应该是没问题的,用其他程序检验过了,你改完运行出来了?
2 年多之前 回复
u013596119
u013596119   Rxr 2016.03.05 22:53
 #include <stdio.h> 
bool mark[100001];
int prime[100001];
int primeSize;
void init(){
    primeSize=0;
    for(int i=2;i<=100000;i++)
    {
        if(mark[i]==true)
        {
        continue;
        }       
        prime[primeSize++]=i;
// if(i>=1000) continue;
        for(int j=i;j<=100000;j+=i)
        {
            mark[j]=true;
        }
    }
}
int main(){
init();
int n;
while(scanf("%d",&n)!=EOF)
{
int ansPrime[30];
int ansNum[30];
int ansSize=0;
for(int 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(int i=0;i<ansSize;i++)
{
ans+=ansNum[i];
}
printf("%d\n",ans);
}
return 0;
}
u013596119
u013596119   Rxr 2016.03.05 22:59

图片说明

上面那个代码的运行结果

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
分解素因数
对一个数分解质因数,使得其满足x=p1^e1*p2^e2*...*pn^en*例一 九度1207 求质因数的个数题目描述:求正整数N(N&amp;gt;1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。输入:可能有多组测试数据,每组测试数据的输入是一个正整数N,(1&amp;lt;N&amp;lt;10^9)。输出:对于每组数据,输出N的质因数的个数。样例输入:120样例输出:5...
机试算法讲解:第26题 分解素因数
/* 问题:质因数个数.求正整数N(>1)的质因数的个数。相同的质因数需要重复计算。如120=2*2*2*3*5,共有5个质因数。 输入:多组测试数据,每组测试数据的输入时一个正整数N,(1<N<10^9) 输入:120 输出:5 注意:1不是N的质因数:若N为质数,N是N的质因数 思路: 用素数筛选法预先筛选出可能在题面所给定的数据范围内成为素因数的素数。程序输入待处理数字n时,依次遍历所有小于
百练 分解因数(递归)
E:分解因数 查看提交统计提问 总时间限制: 1000ms 内存限制: 65536kB 描述给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 输入第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a (1 输出n行,每行输出对应一个输入。输出应是一个正整数,指明
Python因数分解
欢迎访问我的网站:omegaxyz.com把一个合数分解成若干个质因数的乘积的形式,即求质因数的过程叫做分解质因数。 分解质因数只针对合数。(分解质因数也称分解素因数)求一个数分解质因数,要从最小的质数除起,一直除到结果为质数为止。分解质因数的算式叫短除法,和除法的性质差不多,还可以用来求多个个数的公因式。 下面利用生成随机数分解因数的方法:from random import randint
C++分解质因数(获取整数的所有素因子)
算法思想:1、判断是否为素数,如果是,将该数加入素因子集合,返回。2、否则,从2到该数的平方根, 依次将该数分解为两个数的乘积,分别对分解后的数进行判断。3、上述过程递归进行。 C++实现:/* * 获取正整数的所有素因子 * n为正整数 * primes保存所有的素因子,如:8=2*2*2,12=2*2*3 */ static void getPrime(int n, vector
ACM-分解素因子
在一些数学题目中,经常需要将某个数进行分解,以便于发现一些规律然后进行求解。 首先不得不说的一个定理就是唯一分解定理:
分解素因子----唯一分解定理
分解素因子 Time Limit: 1500ms   Memory limit: 10000K  有疑问?点这里^_^ 题目描述 假设x是一个正整数,它的值不超过65535(即1 输入 输入的第一行含一个正整数k (1 输出 每个测试例对应一行输出,输出x的素数乘积表示式,式中的素数从小到大排列,两个素数之间用“*”表示乘法
大数素性测试+大数质因数分解(miller-rabin,Pollard_rho算法)
摘自kuangbin博客可以对一个2^63的素数进行判断。可以分解比较大的数的因子但是不明白一个地方是:大数质因子分解的出的数组factor[]的内容重复原因还有包含2,2不是质数啊?望大神赐教不过以后可以处理大数的素性判定了,还可以处理大数素因子分解了happy#include #include #include #include #include #include using namespac
阶乘的标准分解式中素因数的指数
下面的资料来自:广东江门市华侨中学,赣南师范学院学报论文                           program:(求阶乘含有的某个素数因子的指数) (1)、 int cal(int n,int p) {   if(n     return 0;   else return n/p+cal(n/p,p); }
C++实现质因数分解
质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除(除0以外)的数称之为素数(质数);否则称为合数。根据算术基本定理,每一个比1大的整数,要么本身是一个质数,要么可以写成一系列质数的乘积;而且如果不考虑这些质数在乘积中的顺序,那么写出来的形式是唯一的。最小的质数是2。