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

解题思路:

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

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

#include 
        
         #include
         
          #include
          
           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;}