Программа для вычисления и поиска простых чисел

Первая программа выводит все множители выбранного числа (чисел), если множителей нет, значит число простое:

 
#include <iostream>
using namespace std;
int main () {
    for(int i=1000000000; i <= 1000000030; i++) {
        cout << "Множители числа " << i << ": ";
        for (int j = 2; j < i; j++)
            if( (i%j) == 0) cout << j << " ";
        cout << '\n';
    }
}

Это код выдает все множители чисел от 1 миллиарда до 1млрд30.

На процессоре амд фх8350 4Гц данная прога работает 112 секунд.

Оптимизируем код, чтобы он выводил только простые числа в выбранном промежутке:

#include <iostream>
using namespace std;
int main () {
    int j;
    for(int i=1000000000; i <= 1000000030; i++) {
    //for(int i=2; i <= 100; i++) {
        for (j=2; j <= (i/j); j++)
            if ((i%j) == 0) break;
        if ( j > (i/j) ) cout << " Prime number: " << i << '\n';
    }
}

Этот код работает в тысячу раз быстрее, зо 0.02 секунды найдет простые числа в том же промежутке.

Эта программа определяет, является ли простым число, которое содержится в переменной i, путем последовательного его деления на значения, расположенные между числом 2 и результатом вычисления выражения i/j. (Остановить перебор множителей можно на значении выражения i/j, поскольку число, которое превышает i/j, уже не может быть множителем значения i) Если остаток от деления i/j равен нулю, значит, число i не является простым. Но если внутренний цикл завершится полностью (без досрочного окончания по инструкции break), это означает, что текущее значение переменной i действительно является простым числом.

Если искать простые числа в большем промежутке, например заменить код вначале на:

    unsigned long int j;
    for(unsigned long int i=4000000000; i <= 4000300000; i++) {

то время поиска на амд фх8350 4Гц будет 14 секунд.