Форум программистов, компьютерный форум CyberForum.ru

Всё просто - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Flaber
Сообщений: n/a
09.12.2010, 21:41     Всё просто #1
Напечатать все простые числа, не провосходящее заданое число М.....

вот код

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
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 12:22     Всё просто #21
Цитата Сообщение от volovzi Посмотреть сообщение
Этот метод реализован в моём первом сообщении в этой теме.
Да точно, не заметил.
Про сравнение алгоритмов: один лучше по времени, второй по используемой памяти.

Добавлено через 2 минуты
Кстати, тот "неопознанный" алгоритм можно ускорить.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 13:06     Всё просто #22
valeriikozlov, до определённого предела эратосфен лучше не только по времени, но и по памяти (причём, существенно лучше), что я показал на примере. Точка перехода, в которой эратосфен становится хуже по памяти лежит где-то очень далеко, за пределами типа int. Так что надо указывать, для каких величин он "хуже". Мне эта величина пока неизвестна.

А как можно улучшить другой?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2010, 13:54     Всё просто
Еще ссылки по теме:

Чёрное окно и всё!( C++
просто интересуюсь C++
Не всё то просто, что коротко C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 13:54     Всё просто #23
Цитата Сообщение от volovzi Посмотреть сообщение
А как можно улучшить другой?
У Вас в коде этот "ускоритель" оказывается есть (я его не заметил сразу):
else if (*current_prime * *current_prime > number) break;
Yandex
Объявления
10.12.2010, 13:54     Всё просто
Ответ Создать тему
Опции темы

Текущее время: 01:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru