Project Euler : Problem 3

 Bài này là tìm thừa số nguyên tố lớn nhất của 1 số bất kỳ x.

Gọi x là số bất kỳ

thì x = factor * other

factor là thừa số ta sẽ cho chạy factor từ 2 tới sqrt(x) vì factor  <= other => factor <= sqrt(x)

1. Như vậy nếu other là số nguyên tố thì other sẽ là số nguyên tố lớn nhất

2. Còn nếu other là hợp số thì phân tích tiếp bằng cách chia cho factor cho tới khi other thỏa điều kiện

Factor có thể không phải lúc nào cũng là số nguyên tố nhưng khi đó ta lại gán x = other và lại phân tích tiếp tới khi x chia hết cho factor sẽ quay lại trường hợp 1.

#include <iostream>

int main()

{

unsigned int tests;

std::cin >> tests;

while (tests--)

{

unsigned long long x;

std::cin >> x;

// x can be represented by x=factor*otherFactor

// where factor <= otherFactor

// therefore factor <= sqrt(x)

for (unsigned long long factor = 2; factor * factor <= x; factor++) {

// remove factor, actually it's a prime

// (can occur multiple times, e.g. 20=2*2*5)

while (x % factor == 0 && x != factor) { // note: keep last prime

x /= factor;

}

}

std::cout << x << std::endl;

}

return 0;

}