Посчитать сколько в этом диапазоне простых чисел на С языке

Question

#include<stdio.h>

int countPrimeNumber(int from, int to);

//принимает диапазон чисел от from до to, посчитать сколько в этом диапазоне простых чисел

Подскажите как подобраться к началу задачи, не могу понять( нужно использовать цикл while И условные операторы только(

Answer 1

вам нужно

написать свою функцию bool isPrime(int), которая будет определять является ли число простым или нет
пройти с помощью for от from до to и для каждого числа вызвать isPrime, так определите является ли число простым
при каждом найденном простом числе увеличивать счетчик чисел на 1

А если нужно определить ПРИМЕРНО кол-во простых чисел, то достаточно сделать следующее:

const int count = to / log(to) - from / log(from);

когда у вас from и to будут стремиться к бесконечности, то вы получите точное значение, а так - только приближенное

еще точнее было бы

const int count = li(to) - li(from);

где li - интегральный логарифм, но его нет в стандартной библиотеки, так что особенно не поиспользовать :)

Answer 2

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
 
using namespace std;
 
const int N     = 2000000000;
const int sqrtN = 44721;
 
vector<bool> primes(N+1,true);
 
int main(int argc, const char * argv[])
{
    primes[1] = false;
    for(int i = 0; i <= N; i+= 2) primes[i] = false;
    primes[2] = true;
 
    for(int i = 3; i <= sqrtN; i += 2)
    {
        if (primes[i] == false) continue;
        for(int j = i*i; j <= N; j += i)
        {
            primes[j] = false;
        }
    }

    int total = 0;
    for(int i = 2; i <= N; ++i)
    {
        if (primes[i]) ++total;
    }
    cout << total << endl;
}

На тупом решете Эратосфена, с не самым эффективным vector<bool> у меня для 2000000000 считало 19 секунд.

Запасы для оптимизации, конечно, есть, но небольшие.

Кто напишет для сравнения переборный метод?

БЛОГ НА HUSL

Посчитать сколько в этом диапазоне простых чисел на С языке

Ответы (2 шт):