следующая тема »

[19 Сентябрь 2025, 00:38:37]

Новости, реклама:

[19 Сентябрь 2025, 00:38:37]

Новости, реклама:

[maxposedon]

max_posedon@Melnikov ~ % cat prime.cpp
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

const int val = 1000;

int main()
{
        // primes хранит простые числа
        vector<int> primes;

        // пробегаем диапазон
        for(int i=2; i<val; i++)
        {
                //проверяем просто ли очередное число
                bool prime = true;
                int  sqrt_i= (int)sqrt(i)+1;

                //пытаемся делить на все простые числа, до корня из i
                for(unsigned int j=0; j<primes.size(); j++)
                        if (i%primes[j]==0)
                        {
                                prime = false;
                                break;
                        }
                        else if (primes[j] >= sqrt_i)
                                break;
                //если простое, то заносим
                if (prime)
                        primes.push_back(i);
        }

        //вывод
        for(unsigned int i=0; i<primes.size(); i++)
                cout << primes << " ";
        cout << endl;

        return 0;
}

ну дабы, не было это просто так...
у моего Алгоритма сложность O(N*log(M)),
N - кол-во чисел
M - кол-во простых чисел

для проверки на простоту проверяется все до N, а тока простые и то до корня из числа
поэтому и получаем N*log(M)