将 pascal 代码改写为 c++，使其尽可能高效地工作

Question

所以我得到了这个任务，我有 pascal 代码，我需要弄清楚结果是什么。这不是问题，因为我知道 pascal，但我需要它在 1 秒或更短时间内达到运行，数字最大为 10^9。

readln(N);
counter:=0;
for i:=N-1 downto 1 do begin
    counter:= counter + 1;
    if N mod i = 0 then break;
end;
writeln(counter);

这是我的代码

#include <iostream>

using namespace std;

int main()
{
    int x;
    int counter = 0;
    cin>>x;
    for (int i = 2; i <= x; i++){
        if (x % i == 0){
            counter = x - x / i;
            break;
        }
    }
    cout<<counter;
    return 0;
}

但还是没法满分

Answer 1

10^9这样的数字通常表示竞赛题，需要创造性思维而不是快速CPU...

看，N mod i = 0 表示 N 可以被 i 整除。所以循环计算 N 和它的一个除数之间的数字（可能加一......检查它。）哪个 - 留给你。

Answer 2

重述问题：
1) 计算 F = X 的最大固有因数
2) 输出 X-F

不要直接搜索最大的适当因子，而是应用三个简单的优化（可能需要更高级的东西，但首先看看三个简单的优化是否足够）。

A) 求 S = X 大于 1 的最小因数。输出 X-(X/S)
B) 素数的特例
C) 偶数

的特例

int largest_proper_factor(int X)
{
   if ( X % 2 == 0 ) return X/2;  // Optimize even

   // Note the add of .5 is only needed for non compliant sqrt version that
   // might return a tiny fraction less than the exact answer.
   int last = (int)(.5 + std::sqrt( (double) X )) );

   for ( int i=3; i<=last; i+=2 ) // big savings here because even was optimized earlier
   {
      if ( X % i == 0 ) return X/i;
   }
   return 1;  // special case for prime
}

Answer 3

好的，我得到了我想要的结果：

#include <iostream>
using namespace std;
int main()
{
    int x;
    int counter = 0;
    cin>>x;
    for (int i = 2; i <= x; i++){
        if (x % i == 0){
            counter = x - x / i;
            break;
        }
        if (x / 4 == i){
            i = x - 1;
        }
    }
    cout<<counter;
    return 0;
}

感谢所有帮助过我的人:)

将 pascal 代码改写为 c++，使其尽可能高效地工作

Rephrase pascal code to c++ so it can work as efficient as possible

c++

pascal