c++分解质因数过程
发布网友
共5个回答
热心网友
1、分解质因数定义:
每个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。分解质因数只针对合数。
2、分解质因数方法:
分解质因数的算式叫短除法。求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。
3、分解质因数编程:
#include <iostream>
using namespace std;
class QualityFactor
{
private:
int n;
public:
void QFContract(long a) //用短除法对合数进行分解
{
n = 0; //初始化
while(a>1)
{
for(int i=2;i<=a;i++)
{
if(a%i==0) //短除法
{
a = a/i;
cout << i << " "; //输出因子
break;
}
}
}
cout << endl;
}
};
int main(int argc, char* argv[])
{
QualityFactor QF;
long number;
cout << "输入要解的合数" << endl;
cin>>number;
QF.QFContract(number);
system("pause");
return 0;
}
运行结果：
热心网友
楼主俺有个更快的(楼主的不是分解质因数(分解8后会得2*4).
#include <iostream>#include <time.h>
#include <cmath>
#include <vector>
using namespace std;
void primefactorizationforintlessthan10(unsigned long long n, vector<unsigned long long> &c);
void primefactorizationforintlessthan1000(unsigned long long n, int a[2], vector<unsigned long long> &c);
void primefactorizationforlargeint(unsigned long long n, int b[8], vector<unsigned long long> &c);
void primefactorizationforreallyreallylargeint(unsigned long long n, int d[480], vector<unsigned long long> &c);
int main()
{
unsigned long long n;
int a[] = {5, 7}, b[] = {7, 11, 13, 17, 19, 23, 29, 31}, d[] = {13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,169,173,179,181,191,193,197,199,211,221,223,227,229,233,239,241,247,251,257,263,269,271,277,281,283,2,293,299,307,311,313,317,323,331,337,347,349,353,359,361,367,373,377,379,383,3,391,397,401,403,409,419,421,431,433,437,439,443,449,457,461,463,467,479,481,487,491,493,499,503,509,521,523,527,529,533,541,547,551,557,559,563,569,571,577,587,5,593,599,601,607,611,613,617,619,629,631,1,3,7,653,659,661,667,673,677,683,6,691,697,701,703,709,713,719,727,731,733,739,743,751,757,761,767,769,773,779,787,793,797,799,809,811,817,821,823,827,829,839,841,851,853,857,859,863,871,877,881,883,887,3,9,901,907,911,919,923,929,937,941,943,947,949,953,961,967,971,977,983,9,991,997,1003,1007,1009,1013,1019,1021,1027,1031,1033,1037,1039,1049,1051,1061,1063,1069,1073,1079,1081,1087,1091,1093,1097,1103,1109,1117,1121,1123,1129,1139,1147,1151,1153,1157,1159,1163,1171,1181,1187,11,1193,1201,1207,1213,1217,1219,1223,1229,1231,1237,1241,1247,1249,1259,1261,1271,1273,1277,1279,1283,12,1291,1297,1301,1303,1307,1313,1319,1321,1327,1333,1339,1343,1349,1357,1361,1363,1367,1369,1373,1381,1387,1391,1399,1403,1409,1411,1417,1423,1427,1429,1433,1439,1447,1451,1453,1457,1459,1469,1471,1481,1483,1487,14,1493,1499,1501,1511,1513,1517,1523,1531,1537,1541,1543,1549,1553,1559,1567,1571,1577,1579,1583,1591,1597,1601,1607,1609,1613,1619,1621,1627,1633,1637,13,19,1651,1657,1663,1667,1669,1679,1681,1691,1693,1697,1699,1703,1709,1711,1717,1721,1723,1733,1739,1741,1747,1751,1753,1759,1763,1769,1777,1781,1783,1787,17,1801,1807,1811,1817,1819,1823,1829,1831,1843,1847,1849,1853,1861,1867,1871,1873,1877,1879,18,11,1901,1907,1909,1913,1919,1921,1927,1931,1933,1937,1943,1949,1951,1957,1961,1963,1973,1979,1987,1993,1997,1999,2003,2011,2017,2021,2027,2029,2033,2039,2041,2047,2053,2059,2063,2069,2071,2077,2081,2083,2087,20,2099,2111,2113,2117,2119,2129,2131,2137,2141,2143,2147,2153,2159,2161,2171,2173,2179,2183,2197,2201,2203,2207,2209,2213,2221,2227,2231,2237,2239,2243,2249,2251,2257,2263,2267,2269,2273,2279,2281,2287,2291,2293,2297,2309,2311};
char cont;
clock_t t;
do
{
vector<unsigned long long> c(2, 0);
cout << "Please enter the positive integer to be factorized:";
cin >> n;
cout << "\nThe prime factors and respective exponents for n is/are:\n";
t = clock();
switch (int (log10(n)))
{
case 0: primefactorizationforintlessthan10(n, c); break;
case 1: primefactorizationforintlessthan1000(n, a, c); break;
case 2: primefactorizationforintlessthan1000(n, a, c); break;
case 3: primefactorizationforlargeint(n, b, c); break;
case 4: primefactorizationforlargeint(n, b, c); break;
case 5: primefactorizationforlargeint(n, b, c); break;
default: primefactorizationforreallyreallylargeint(n, d, c); break;
}
t = clock() - t;
for (int p = 1; p < (c.size() / 2); p++)
{
cout << endl;
cout << " " << c[2*p];
if (c[2*p+1]!=1)
cout << " ^ " << c[2*p+1];
}
cout << "\n\ntime used = " << t << " ms\ncontinue? (y/n)";
cin >> cont;
cout << endl;
} while (cont == 'y');
return 0;
}
void primefactorizationforintlessthan10(unsigned long long n, vector<unsigned long long> &c)
{
for (int p = 2; p < 8; p++)
{
if (n % p == 0)
{
start:
n = n / p;
if (c[c.size()-2] == p)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = p;
c[c.size()-1]++;
}
if(n % p == 0)
goto start;
}
}
}
void primefactorizationforintlessthan1000(unsigned long long n, int a[2], vector<unsigned long long> &c)
{
int j = 0, l;
if (n % 2 == 0)
{
start2:
n = n / 2;
if (c[c.size()-2] == 2)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 2;
c[c.size()-1]++;
}
if (n % 2 == 0)
goto start2;
}
if (n % 3 == 0)
{
start3:
n = n / 3;
if (c[c.size()-2] == 3)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 3;
c[c.size()-1]++;
}
if (n % 3 == 0)
goto start3;
}
while (j <= int (sqrt(n) / 6))
{
for (int k = 0; k < 2; k++)
{
l = 6 * j + a[k];
if (n % l == 0)
{
start:
n = n / l;
if (c[c.size()-2] == l)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = l;
c[c.size()-1]++;
}
if (n % l == 0)
goto start;
}
}
j++;
}
if (n != 1)
{
c.resize(c.size() + 2);
c[c.size()-2] = n;
c[c.size()-1]++;
}
}
void primefactorizationforlargeint(unsigned long long n, int b[8], vector<unsigned long long> &c)
{
int j = 0, l;
if (n % 2 == 0)
{
start2:
n = n / 2;
if (c[c.size()-2] == 2)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 2;
c[c.size()-1]++;
}
if (n % 2 == 0)
goto start2;
}
if (n % 3 == 0)
{
start3:
n = n / 3;
if (c[c.size()-2] == 3)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 3;
c[c.size()-1]++;
}
if (n % 3 == 0)
goto start3;
}
if (n % 5 == 0)
{
start5:
n = n / 5;
if (c[c.size()-2] == 5)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 5;
c[c.size()-1]++;
}
if (n % 5 == 0)
goto start5;
}
while (j <= int (sqrt(n) / 30))
{
for (int k = 0; k < 8; k++)
{
l = 30 * j + b[k];
if (n % l == 0)
{
start:
n = n / l;
if (c[c.size()-2] == l)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = l;
c[c.size()-1]++;
}
if (n % l == 0)
goto start;
}
}
j++;
}
if (n != 1)
{
c.resize(c.size() + 2);
c[c.size()-2] = n;
c[c.size()-1]++;
}
}
void primefactorizationforreallyreallylargeint(unsigned long long n, int d[480], vector<unsigned long long> &c)
{
int j = 0, l;
if (n % 2 == 0)
{
start2:
n = n / 2;
if (c[c.size()-2] == 2)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 2;
c[c.size()-1]++;
}
if (n % 2 == 0)
goto start2;
}
if (n % 3 == 0)
{
start3:
n = n / 3;
if (c[c.size()-2] == 3)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 3;
c[c.size()-1]++;
}
if (n % 3 == 0)
goto start3;
}
if (n % 5 == 0)
{
start5:
n = n / 5;
if (c[c.size()-2] == 5)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 5;
c[c.size()-1]++;
}
if (n % 5 == 0)
goto start5;
}
if (n % 7 == 0)
{
start7:
n = n / 7;
if (c[c.size()-2] == 7)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 7;
c[c.size()-1]++;
}
if (n % 7 == 0)
goto start7;
}
if (n % 11 == 0)
{
start11:
n = n / 11;
if (c[c.size()-2] == 11)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = 11;
c[c.size()-1]++;
}
if (n % 11 == 0)
goto start11;
}
while (j <= int (sqrt(n) / 2310))
{
for (int k = 0; k < 480; k++)
{
l = 2310 * j + d[k];
if (n % l == 0)
{
start:
n = n / l;
if (c[c.size()-2] == l)
c[c.size()-1]++;
else
{
c.resize(c.size() + 2);
c[c.size()-2] = l;
c[c.size()-1]++;
}
if (n % l == 0)
goto start;
}
}
j++;
}
if (n != 1)
{
c.resize(c.size() + 2);
c[c.size()-2] = n;
c[c.size()-1]++;
}
}
热心网友
你把cout前还有else前用大括号括起来，作为一个程序段，不然if到cout句就终止了，后面的else没有匹配的if句。
热心网友
#include <iostream>
#include <stdafx.h>
using namespace std;
int main()
{
int n,c;
cout<<"please input a number"<<endl;
cin>>n>>c;
cout<<"the result is:"<<" ";
cout<<n<<"=";
while (n>c)
{
if (n%c==0)
{
cout<<c<<"*";
n=n/c;
}
else
c++;
}
cout<<n;
while (1);
return 0;
}
结果：
please input a number
输入两个数字用空格分割
热心网友
#include <iostream>
using namespace std;
int main()
{
int n,c;
cout<<"please input a number";
cin>>n,c;
cout<<"the result is:"<<" ";
cout<<n<<"=";
while (n>c)
{
if (n%c==0)
{cout<<c<<"*";
n=n/c;}
else
{ c++;}
}
cout<<n;
while (1);
return 0;
}
