## Extra 1

This article will not directly provide the answer code, but will give you a few hints and explain which ideas should be inappropriate.

## Description

[Problem link](https://oj.cerana.tech/contest/6/problem/1)

Check if a number 'n' is a Carrey's number.

The essence of this question is how to quickly factorize a number into prime factors.

## Approach 1: Brute force search (TLE)

long long sum=0;
for(long long i=2;i<=n;++i){
    while(n%i==0){
        n/=i;
        sum+=i;
    }
}

Although the above code seems to be able to quickly converge on some cases, when it encounters some large factors, it must be executed for a very long time.

e.g. n = f1^5 * f2^4 * f3^7 * .... * fx;

This code must at least run to fx. When fx is very large, it will time out.

## Approach 2: Random guess (0.0...01% AC)

Think carefully about the following code:

long long sum=0;
do{
    long long x=rand(2~n);
    if(n%x==0){
        n/=x;
        sum+=x;
    }
}while(n!=1);

As long as you are lucky enough, rand will appear prime numbers every time, and they happen to be factors of n.

Although this code looks like it was written by a monkey, it is actually the right path.

## To be continued...