Производительность при достижении 65535 резко возрастает по сравнению с другими входами

Question

Вот код ниже, чтобы получить следующее простое число на основе ввода.Я также измеряю, сколько времени занимает наносекунда для завершения операции.

Я использую C ++ в Visual Studio 2017 (выпуск для сообщества).Мои результаты, полученные при вводе некоторых чисел, составляют от 300 наносекунд для небольших чисел (1-100) до 800 наносекунд (1 000 000 000 и выше).Однако, если я введу 65535, я получу 97767 наносекунд.Но когда я вводил 65533, это 438 наносекунд, а когда я вводил 65539, это 487 наносекунд.

Мой вопрос: почему 65535 требует больше времени для вычисления, но для другого числа выше или ниже его значительно меньше?

#include "stdafx.h"
#include <string>
#include <iostream>
#include <chrono>

bool isPrime(int num)
{
    int divisor = 3;
    while (divisor != INT_MAX)
    {
        if (divisor % 2 == 0)
        {
            divisor++;
        }
        if (num % divisor == 0)
        {
            return true;
        }
        divisor += 2;
    }
    return false;
}
int findNextPrime(int num) 
{
    while (num != INT_MAX) 
    {
        if (num % 2 == 0) 
        {
            num++;
        }
        else 
        {
            num += 2;
        }

        if (isPrime(num))
        {
            return num;
        }
        else
        {
            num++;
        }
    }

    return -1;
}

int main()
{
    int candidatePrime;
    std::string str;
    std::cin >> candidatePrime;
    const auto start = std::chrono::high_resolution_clock::now();
    const int nextPrime = findNextPrime(candidatePrime);
    const auto end = std::chrono::high_resolution_clock::now();
    std::cout << nextPrime << std::endl;
    std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count()
        << " nanoseconds" << std::endl;
    std::cin >> str;
    return 0;
}

Answer 1

Прежде всего, ваша bool isPrime(int num) доза не проверяет, является ли число простым или нет. Попробуйте это с 25 например. Сначала вы должны попытаться это исправить. Также посмотрите здесь Определение, является ли число простым

Но чтобы ответить на ваш вопрос: Когда вы вводите 65533, вы вызываете is_prime с 65535, который делится на 3, поэтому ваш цикл while (divisor != INT_MAX) будет выполняться только 1 раз.

Когда вы вводите 65535, вы вызываете is_prime с 65537, который является простым числом, поэтому ваш цикл while (divisor != INT_MAX) будет выполняться ~ 32767 раз.

Это нормально, что для простых чисел ваша функция будет работать дольше.