Performance when reaching 65535 jumps wildly compared to other input

Question

Here's some code below to get the next prime number based on the input. I'm measuring as well how long it takes in nanoseconds for the operation to complete.

I am using C++ in Visual Studio 2017 (Community edition). My results from some numbers I input are from 300 nanoseconds for small numbers (1-100) to 800 nanoseconds (1,000,000,000 and higher). However, if I input 65535, I get 97767 nanoseconds. But when I input 65533, it's 438 nanoseconds, and when I input 65539, it's 487 nanoseconds.

My question is: why does 65535 take a larger time to compute, but for other number above or below it, it's significantly lower?

#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

First of all your bool isPrime(int num) dose not check if a number is prime or not. Try it with 25 for example. You should first try to fix that. Also have a look here Determining if a number is prime

But to answer your question: When you input 65533, you call is_prime with 65535 which is divisible by 3, so your while (divisor != INT_MAX) loop will only run 1 time.

When you input 65535, you call is_prime with 65537 which is a prime number, so your while (divisor != INT_MAX) loop will run ~32767 times.

It's only normal that for prime numbers your function will take longer to run.