PE - 003

Posted by WildCow on November 12, 2018

题面


The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?





解决


筛一下质因子然后除一除


#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1e6+7;

char v[N];
int pri[N];
int len;

void Init_pri(int n)
{
	len = 0;
    memset(v,0,sizeof(v));
    for(int i = 2; i < n; i++)
    {
        if(v[i] == 0)
            pri[len++] = i;
        for(int j = 0; j<len && pri[j]*i<n; j++){
            v[i*pri[j]] = true;
            if(i%pri[j]==0) break;
        }
    }
}

int main(int argc, char const *argv[])
{
	LL x;

	x = 600851475143;
	Init_pri(N);
	for(int i = 0; i < len; i ++){
		while(x % pri[i] == 0){
			x /= pri[i];
		}
	}
	cout << x << endl;

	return 0;
}