素数分解问题
我要把任意一个整数分解成其质因子的乘积。
我想到的算法是顺次用质子去除它，直到剩下的数等于1。
所以我想先把所有质数存在一个数组里，再逐个调用。
例如：
120=2^3*3^1*5^1
所以：素数表：
2 3 5
3 1 1
请问代码怎么做阿？
[解决办法]
先要获得质数表
函数:
#include <iostream>
using namespace std;
void getprime(int *prime)
{
int t[100];//获得100内所有的素数
int i,d;
for (i=2;i <=99;i++)
t[i]=1;
for (i=2;i <=99;i++)
if (t[i]==1)
{
for (d=2*i;d <=99;d+=i)
t[d]=0;
*prime++ = i;
}
}
int yourfun(int *table,int *prime,long t)
{
//table作为存储指数表的数组，prime是质数表，t就是输入的数
int s=0;//返回有多少质因数
while (t!=1)
{
table[s]=0;
while (t%prime[s]==0)
{
t/=prime[s];
table[s]++;
}
++s;
}
return s;
}
int main()
{
//先调用getprime()
int p[100],t[100];//质数表和因子表
int d,i;
getprime(p);
d = yourfun(t,p,120);
for (i=0;i <=d-1;i++)
{
cout < <t[i] < < ' ';
}
cout < <endl;
return 0;
}
你会看到 3 1 1的输出
[解决办法]
#include <map>
#include <iostream>
#include <cstdlib>
using namespace std;
bool isprime(int i) //测试是否是质数
{
int x;
for(x=3; x <i/2; x+=2)
if(i%x ==0)return 0;
return 1;
}
int main(int argc, char* argv[])
{
int n, i;
map <int, int> intmap;
cout < < "please input a number: ";
cin> > n;
for(i=2;i <=n;i++)
{
if(isprime(i)) //如果是质数
{
if(n%i == 0) //如果整除
{
intmap.insert(make_pair(i, 1)); //插入 map
n /= i;
while(n%i == 0)intmap[i]++, n/=i; //循环计数
}
}
}
//下面是遍历输出
map <int, int> ::iterator it;
for(it=intmap.begin(); it!=intmap.end(); it++)
cout < <it-> first < < " ";
cout < <endl;
for(it=intmap.begin(); it!=intmap.end(); it++)
cout < <it-> second < < " ";
cout < <endl;
system( "pause ");
return 0;
}
[解决办法]
http://blog.joycode.com/jiangsheng/archive/2006/06/02/76755.aspx
