我遇到了一個有趣的問題。輸入是 1..n 中的一個數字，其中 n <= 10^9。所以你需要通過改變它的數字來制作一個素數。此外，您需要更改盡可能少的數字，如果有多個這樣的選項，那么您需要最小化數字。例如 10，答案是 11。
這個任務通過了我所有的測驗，并在檢查系統中被接受。但我的決定似乎很奇怪，也很古怪。
我考慮了一些小數的情況，考慮到素數經常出現，我決定先迭代一個數字，然后用 0..9 中的任何一個數字替換它。但是這個解決方案在第 5 次測驗中失敗了。之后，我決定添加對第二個數字的搜索，然后解決方案通過了測驗。
事實證明，我的解決方案適用于漸近 len(n)^2 81 sqrt(n)。哪個好。但我絕對無法證明為什么 2 位數就足夠了。突然有一些數字需要替換 3 位或更多位。
請幫我弄清楚為什么這是真的，或者幫我想出一些正常的解決方案。
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
bool prost(int x)
{
if (x <= 1)
{
return false;
}
for (int i = 2; i <= (int)sqrt(x); i )
{
if (x % i == 0)
{
return false;
}
}
return true;
}
int main()
{
string s;
cin >> s;
if (prost(stoi(s)))
{
cout << s << endl;
return 0;
}
string ans = "";
for (int i = 0; i < s.length(); i )
{
ans = '9';
}
for (int i = 0; i < s.length(); i )
{
for (char j = '0'; j <= '9'; j )
{
if (i == 0 && j == '0')
{
continue;
}
char buff = s[i];
s[i] = j;
if (prost(stoi(s)))
{
ans = min(ans, s);
}
s[i] = buff;
}
}
string shab = "";
for (int i = 0; i < s.length(); i )
{
shab = '9';
}
if (shab == ans)
{
for (int i = 0; i < s.length(); i )
{
for (int j = i 1; j < s.length(); j )
{
for (char ii = '0'; ii <= '9'; ii )
{
for (char jj = '0'; jj <= '9'; jj )
{
char buff1 = s[i];
char buff2 = s[j];
if (i == 0 && ii == '0') continue;
s[i] = ii;
s[j] = jj;
if (prost(stoi(s)))
{
ans = min(ans, s);
}
s[i] = buff1;
s[j] = buff2;
}
}
}
}
if (ans == shab)
{
cout << 1 / 0;
return -0;
}
}
cout << ans << endl;
return 0;
}uj5u.com熱心網友回復：
我認為這可以通過一些觀察/因素來解釋。
- 大多數世紀 (
xxxx00 to xxxx99) 至少有一個素數。 - 沒有素數的第一世紀是
1671800. - 沒有素數的第一個千年是
13893290219204000（足夠大于10^9）。
如果你把這些因素結合起來，就很容易理解為什么大多數數字可以通過改變兩位數來變成素數（因為很多世紀都有素數）。如果世紀沒有素數，那么改變三位數可以保證給出一個解決方案，因為給定范圍內的每個千年都有一個素數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446394.html