Перефразируйте код паскаля в c ++, чтобы он работал максимально эффективно

Question

Перефразируйте код паскаля в c ++, чтобы он работал максимально эффективно

Таким образом, я получил эту задачу, где у меня есть Паскаль-код, и мне нужно получить результат. Это не будет проблемой, потому что я знаю паскаль, но мне нужно, чтобы он работал за 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;
}

но он все еще не может получить максимальный балл.

-6

c++pascal

Решение

Другие решения

Числа вроде 10 ^ 9 обычно указывают на проблемы конкурса, которые требуют творческого мышления вместо быстрого процессора …

Увидеть, N mod i = 0 средства N делится на i, Таким образом, цикл считает числа между N и один из его делителей (возможно, плюс один … Проверьте это.) Какой из них — остается для вас.

0

Хорошо, я получил результат, который я хотел:

#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;
}

Спасибо всем, кто помог мне 🙂

-1

Источник

Accepted Answer

Пересмотрите проблему:
1) Вычислить F = самый большой собственный коэффициент X
2) Выход X-F

Вместо непосредственного поиска наиболее подходящего фактора примените три тривиальные оптимизации (возможно, потребуется что-то более продвинутое, но сначала посмотрите, достаточно ли трех тривиальных оптимизаций).

A) Найти S = наименьший коэффициент X больше 1. Выход X- (X / S)
Б) Особый случай для премьер
В) Особый случай даже

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
}

2