做网站的相关协议/经典营销案例100例

把一个数分解成n*m的形式,一定存在

解题思路:

一个大于1的正整数最小因数一定是素数

ac时间80ms,感觉慢了,可惜看不到0ms的大神代码

#include <iostream>
#include<memory.h>
#include<stdio.h>
using namespace std;const int N = 10000000;int p[N];
int pl = 0;void initPrime()
{memset(p, -1, sizeof(p));int i, j;for (i = 2; i <= N; i++){if (p[i] == -1)p[pl++] = i;for (j = 0; j < pl; j++){if (p[j] * i >= N){break;}p[p[j] * i] = 0;if (i % p[j] == 0)break;}}
}
int main()
{freopen("d:\\1.txt", "r", stdin);initPrime();int n;int t = 1;int c;cin >> c;while (c--){cin >> n;printf("Case #%d: ", t);int m, k, j;for (int i = 0; i < pl; i++){if (n % p[i] == 0){j = i;break;}}m = p[j];k = n / m;cout << n << " = " << m << " * " << k;for (int i = 0; i < pl; i++){if (k % p[i] == 0){j = i;break;}}m = m * p[j];k = k / p[j];cout << " = " << m << " * " << k;cout << endl;t++;}return 0;
}