问题 B: 质因数分解

时间限制1 Sec  内存限制128 MB
提交32  解决22
[
提交][状态][讨论版][命题人:150112200121][Edit] [TestData]

题目链接:http://acm.ocrosoft.com/problem.php?cid=1701&pid=1

题目描述

已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。

输入

输入只有一行,包含一个正整数 n

对于 30% 的数据,n1000
对于全部数据,6n2×109
 

输出

输出只有一行,包含一个正整数 p,即较大的那个质数。

样例输入

21

样例输出

7

思路:由于数据量很大,用试除法套线性筛。

代码:

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mod 100003

#define maxn 1000005

#define INF 0x3f3f3f3f

int v[maxn], prime[maxn];

int m = 0;

void xianxing(int n)//线性筛

{

    for (int i = 2; i <= n; i++)

    {

         if (v[i] == 0)

         {

             v[i] = i;

             prime[++m] = i;

         }

         for (int j = 1; j <= m; j++)

         {

             if (prime[j] > v[i] || prime[j] * i > n)

             {

                  break;

             }

             v[i*prime[j]] = prime[j];

         }

    }

    /*for (int i = 1; i <= m; i++)

    {

         cout << prime[i] << " ";

    }*/

}

int main()

{

    xianxing(50000);

    int n;

    cin >> n;

    for (int i = 1; i <= m; i++)//试除法套线性筛

    {

         if (n%prime[i] == 0)

         {

             cout << n / prime[i];

             break;

         }

    }

    return 0;

}