Всё просто

@flaber · Регистрация: 18.08.2014

Студворк — интернет-сервис помощи студентам

Напечатать все простые числа, не провосходящее заданое число М.....

вот код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
 
#define N 150
 
int main(void)
{
    int m,i,j,k,q,P[N];
    
    std::cin >> m;
    
    if(m>=2) std::cout <<"2"<<std::endl;
    if(m>=3)  std::cout <<"3"<<std::endl;
 
    P[k=0]=3;
 
    for(i=5; i<=m; i+=2)
    {
        for (j=0; j<=k; j++)
        {
            q=P[j]; if(q*q>i) break;
            if(!(i)) goto NP; 
        }
        std::cout << i <<std::endl;
        if (k<N-1) P[++k]=i;
NP:;}       
}

например у меня выводит 2 3 5 7 9
но 9 не простое число...

Добавлено через 52 секунды
то есть где то ошибка но где??

valeriikozlov · 10.12.2010, 12:22

Сообщение от volovzi

Этот метод реализован в моём первом сообщении в этой теме.

Да точно, не заметил.
Про сравнение алгоритмов: один лучше по времени, второй по используемой памяти.

Добавлено через 2 минуты
Кстати, тот "неопознанный" алгоритм можно ускорить.

@volovzi · 10.12.2010, 13:06

valeriikozlov, до определённого предела эратосфен лучше не только по времени, но и по памяти (причём, существенно лучше), что я показал на примере. Точка перехода, в которой эратосфен становится хуже по памяти лежит где-то очень далеко, за пределами типа int. Так что надо указывать, для каких величин он "хуже". Мне эта величина пока неизвестна.

А как можно улучшить другой?

valeriikozlov · 10.12.2010, 13:54

Сообщение от volovzi

А как можно улучшить другой?

У Вас в коде этот "ускоритель" оказывается есть (я его не заметил сразу):

else if (*current_prime * *current_prime > number) break;

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	10.12.2010, 13:06
	valeriikozlov, до определённого предела эратосфен лучше не только по времени, но и по памяти (причём, существенно лучше), что я показал на примере. Точка перехода, в которой эратосфен становится хуже по памяти лежит где-то очень далеко, за пределами типа int. Так что надо указывать, для каких величин он "хуже". Мне эта величина пока неизвестна. А как можно улучшить другой? 0

Опции темы