问题 B: 质因数分解

问题 B: 质因数分解

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

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

题目描述

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

输入

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

对于 30% 的数据，n≤1000；
对于全部数据，6≤n≤2×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;

}