算法基础—分解质因数
发布时间
阅读量：
阅读量
分解质因数
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
数据规模和约定
2<=a<=b<=10000
感觉这个思路确实不复杂，在筛选素数的过程中先检查提取出来的素数集合是否能整除目标数值；如果不能整除，则继续循环直到满足条件再进行一次判断。
基于算法框架的方案和采用递归方法的方案是两种不同的解决途径。
#include <iostream>
using namespace std;
int main()
{
int a, b;
cin>>a>>b;
for(int i=a; i<=b; i++)
{
cout<<i<<'=';
int j, temp=i;
int k=1;//判断前面是不是要加乘号。
for(j=2; j<=temp; j++)
{
while(temp!=j)//判断是不是素数。
{
if(temp%j==0)//如果不是素数。
{
if(k==1)//如果第一次输出
{
cout<<j;
temp/=j;
k=0;
}
else
{
cout<<'*'<<j;
temp/=j;
}
}
else
break;
}
}
if(k==1)
cout<<temp<<endl;
else
cout<<'*'<<temp<<endl;
}
return 0;
}
c
 #include <iostream>
#include <cmath>
using namespace std;
int i=0;//判断是否要输出乘号。
int isprime(int n)//判断素数
{
if(n==1)
return 0;
for(int i=2; i<=sqrt(n); i++)
if(n%i==0)
return 0;
return 1;
}
int result(int n)
{
if(isprime(n))
{
if(::i)//判断是否要加乘号::全局变量
{
cout<<'*'<<n;
::i=1;
}
else
{
cout<<n;
}
}
else
{
for(int i=2; i<n; i++)
{
if(n%i==0)
{
if(::i)
{
cout<<'*'<<i;
}
else
{
cout<<i;
::i=1;
}
if(isprime(n/i))
cout<<'*'<<n/i;
else
{
result(n/i);
}
break;
}
}
}
}
int main()
{
int n, m;
cin>>n>>m;
for(int i=n; i<=m; i++)
{
cout<<i<<'=';
result(i);
cout<<endl;
::i=0;
}
return 0;
}
c
全部评论 (0)
还没有任何评论哟~