uva-10879-因数分解

把一个数分解成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;
}