素数判定においてCPUキャッシュを使ったほうが早いのか調査

CPUキャッシュから外れたほうが遅いかもしれないので一応調べてみた
※CPUキャッシュが効いてるのかはよく知らないのでプログラムはほぼオリジナルからの模写

プログラムはこんな感じ

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> vecPrime;
	vecPrime.push_back(2);

	// 最大数の入力
	std::cout << "素数調査の最大数を入力してください(２以上の整数)" << std::endl;

	int max;
	do {
		std::cin >> max;
	} while (max < 2);

	// 結果表題表示
	std::cout << std::endl << max << "以下の素数は以下の通り" << std::endl << std::endl;

	clock_t start = clock();

	// 素数チェック
	for (int i = 3; i <= max; i++) {
		bool isPrime = true;

		for (auto div : vecPrime) {
// trueだとCPUキャッシュが効くやつっぽい。falseだと素数判定最適化(調べる値のルートまでしか調べない)
#if true
			isPrime = (i / div * div != i);
#else
			isPrime = (div > sqrt(i) || (i / div * div != i));
#endif
			if (!isPrime) break;
		}
		if (!isPrime) continue;

		vecPrime.push_back(i);
//		std::cout << i << ", "; // 時間計測時はこの行をコメントアウト
	}

	// 最終結果
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC * 1000.0;
	std::cout << std::endl << time << "ms" << std::endl;

	std::cout << std::endl << std::endl << "素数が" << vecPrime.size() << "個見つかりました" << std::endl;

	return EXIT_SUCCESS;
}

調べる値が100000での結果

• CPUキャッシュが効く方
  
• 調べる値のルートまでしか調べない
  

調べる値が1000000での結果

• CPUキャッシュが効く方
  
• 調べる値のルートまでしか調べない
  

※オリジナルの記事でも実行時間が４秒台なので間違いはないはず…

結果、範囲最適化のほうが時間かからない