模拟+素数筛

由于$x$不超过$10^9$，所以，如果其为一个完全平方数，则$\sqrt{x}\le\sqrt{10^9}$。同样的，当$x$不是素数时，其最小因子也不会超过$\sqrt{10^9}$。

反证：假设其最小因子$p\gt \sqrt{10^9}$，则有$p'=x/p\lt\sqrt{10^9}$。矛盾。

所以我们需要筛出$\sqrt{10^9}$以内的素数，如果$x$是合数，则在筛出的素数中找最小素因子。如果$x$是素数，那么其要么就在筛出的素数里面，要么就是可以通过$\sqrt{N}$的计算来判断其是否是素数。

假设一个数所有因子均为2，有$2^{30}\gt10^9$，操作一的次数和操作二的次数最多一样，而操作二不会超过30次，所以不会超时。

代码

C++

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

int x;
int prime[32000],cnt=0;
bool mark[32000];
int ans=0;

void getPrime(){
	int index = 0;  
    for(int i = 2; i < 32000; i++){  
        if(mark[i] == 0){
        	prime[++cnt] = i;
		}
        for(int j = 1; j <= cnt && prime[j] * i < 32000; j++){  
            mark[i * prime[j]] = 1;  
            if(i % prime[j] == 0) break;  
        }  
    } 
}

bool isPrime(int x){
	for(int i=2;i*i<=x;++i){
		if(x%i==0) return false;
	}
	return true;
}

bool check(int x){
	int tmp = sqrt(x);
	if(tmp*tmp==x) return true;
	return false;
}

int main(){
	cin>>x;
	getPrime();
	while(check(x)==false){
		if((x<32000&&!mark[x])||isPrime(x)){
			x-=1;
			ans++;
		}else{
			for(int i=1;i<=cnt;++i){
				if(x%prime[i]==0){
					x/=prime[i];
					ans++;
					break;
				}
			}
		}
	}
	cout<<ans;
	
	return 0;
}

java

import java.util.*;

public class Main {

    static int x;
    static int[] prime = new int[32000];
    static int cnt = 0;
    static boolean[] mark = new boolean[32000];
    static int ans = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        x = scanner.nextInt();
        getPrime();
        while (!check(x)) {
            if ((x < 32000 && !mark[x]) || isPrime(x)) {
                x -= 1;
                ans++;
            } else {
                for (int i = 1; i <= cnt; i++) {
                    if (x % prime[i] == 0) {
                        x /= prime[i];
                        ans++;
                        break;
                    }
                }
            }
        }
        System.out.println(ans);
        scanner.close();
    }

    // 获取素数
    static void getPrime() {
        for (int i = 2; i < 32000; i++) {
            if (!mark[i]) {
                prime[++cnt] = i;
            }
            for (int j = 1; j <= cnt && prime[j] * i < 32000; j++) {
                mark[i * prime[j]] = true;
                if (i % prime[j] == 0) break;
            }
        }
    }

    // 判断是否是素数
    static boolean isPrime(int x) {
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }

    // 检查是否为完全平方数
    static boolean check(int x) {
        int tmp = (int) Math.sqrt(x);
        return tmp * tmp == x;
    }
}

python

# 考点1：10^9 中其实只有sqrt(10^9)个数需要去分析是否为素数
# 考点2：埃氏筛
# 考点3：判断是否为质数
# 考点4：找到最小质因数，一般次数都比较少，不然需要用二分

from math import sqrt

N = 32000
primes = []
is_p = [False for _ in range(N + 1)]

def ols(N):
    for i in range(2, N):
        if not is_p[i]:
            primes.append(i)
        for prime in primes:
            if prime * i > N:
                break
            is_p[prime * i] = True
            if i % prime == 0:
                break

def check(x):
    for prime in primes:
        if prime >= x:
            break
        tmp = x // prime
        if tmp * prime == x:
            return False
    return True

x = int(input())
ols(N)

ans = 0
while True:
    # 
    if x == int(sqrt(x)) ** 2:
        break
    else:
        if check(x):
            x -= 1
            ans += 1
        else:
            for prime in primes:
                if x % prime == 0:
                    x //= prime
                    ans += 1
                    break
        

print(ans)

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

小红拿到一个整数$x$，并希望通过如下两个操作将$x$变为完全平方数。

1. 如$x$是素数，则将其减1
2. 否则，将其除以自己最小的素因子。

小红需要操作多少次？

输入描述

一个正整数$x$

$1\le x\le 10^9$

输出描述

一个整数，表示操作次数。

样例

输入

5

输出

1

输入

20

输出

3