Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
flaber
0 / 0 / 0
Регистрация: 18.08.2014
Сообщений: 19
#1

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

09.12.2010, 21:41. Просмотров 1178. Ответов 22
Метки нет (Все метки)

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

вот код

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 секунды
то есть где то ошибка но где??
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2010, 21:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Всё просто (C++):

НЕ всё так просто - C++
Привет всем, не могли бы Вы мне помочь решить одну задачку, с ней не всё так просто, как кажется на первый взгляд, я с ней морочу голову...

Не всё то просто, что коротко - C++
На сайте http://www.e-olimp.com.ua/ решение этой задачи не засчитывается. Исправьте, пожалуйста, ошибку Вот условие Вам даны целые...

сегодня наконец то понял что такое КЛАСС, и ОБЪЕКТ. понято всё, кроме одного - зачем всё это? в смысле, можно же без этого? так зачем жизнь усложнять? - C++
сегодня наконец то понял что такое КЛАСС, и ОБЪЕКТ. понято всё, кроме одного - зачем всё это? в смысле, можно же без этого? так зачем жизнь...

просто 2*2 - C++
написать прогу, выводящую элементы массива в порядке возрастания!!! Добавлено через 14 минут Неужели никто не ответит

просто интересуюсь - C++
1. надо сделать чтобы полностью рандомные числа неповторялись... srand(time(NULL)) написал. 2. какую сортировку лучше всего...

Очень просто(x^3) - C++
А как записать Х в кубе?

22
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:37 #16
Нужно!
0
valeriikozlov
Эксперт С++
4674 / 2500 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:42 #17
Хорошо,
Если честно, то метод Эратосфена не считаю оптимальным (по объему выделяемой памяти), не помню чей метод, но считаю его оптимальней:
если заданное число не делится без остатка на все простые числа меньше его, то оно само простое число.
1
ForEveR
В астрале
Эксперт С++
7983 / 4742 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
10.12.2010, 02:54 #18
Интересно. Надо запомнить.
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
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
bool isSimple(int a, const std::vector<int>& Vec)
{
    for(std::vector<int>::const_iterator Iter=Vec.begin();
        Iter!=Vec.end(); 
        ++Iter)
    {
        if(a % *Iter == 0)
            return false;
    }
    return true;
}
 
int main()
{
    int m=0;
    std::cout<<"Enter m: ";
    std::cin>>m;
    int i=2;
    std::vector<int> Vec;
    while(1)
    {
        if(i > m)
            break;
        if(isSimple(i, Vec))
            Vec.push_back(i);
        ++i;
    }
    std::copy(Vec.begin(), Vec.end(), std::ostream_iterator<int>(std::cout, "\n"));
    system("pause");
    return 0;
}
0
valeriikozlov
Эксперт С++
4674 / 2500 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 03:01 #19
Но по времени быстрее как раз алгоритм Эратосфена....
0
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 12:01 #20
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Хорошо,
Если честно, то метод Эратосфена не считаю оптимальным (по объему выделяемой памяти), не помню чей метод, но считаю его оптимальней:
если заданное число не делится без остатка на все простые числа меньше его, то оно само простое число.
Этот метод реализован в моём первом сообщении в этой теме.

Сравнение этого метода и моей же реализации эратосфеновского:
Простые числа до 10 млн.:
2596 кб, 8 с.
1220 кб, 3,8 с.

До 100 млн.:
22 Мб, 174,93 с.
12 Мб, 45,457 с.

Так что утверждение насчёт неоптимальности решета эратосфена весьма сомнительно. Проверять точно лень (очень долго ждать), но подозреваю, что его неоптимальность начнёт сказываться только за пределами типа int.
0
valeriikozlov
Эксперт С++
4674 / 2500 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 12:22 #21
Цитата Сообщение от volovzi Посмотреть сообщение
Этот метод реализован в моём первом сообщении в этой теме.
Да точно, не заметил.
Про сравнение алгоритмов: один лучше по времени, второй по используемой памяти.

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

А как можно улучшить другой?
0
valeriikozlov
Эксперт С++
4674 / 2500 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 13:54 #23
Цитата Сообщение от volovzi Посмотреть сообщение
А как можно улучшить другой?
У Вас в коде этот "ускоритель" оказывается есть (я его не заметил сразу):
else if (*current_prime * *current_prime > number) break;
0
10.12.2010, 13:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2010, 13:54
Привет! Вот еще темы с ответами:

просто так - C++
int onscreen(FILE *f) { setlocale(LC_ALL,&quot;Rus&quot;); system (&quot;cls&quot;); // очистка консоли rewind (f); // перевод указателя в начало файла...

Просто посмотрите! - C++
Ув. дамы и госопода просьба к вам которые знают и могут помочь в задачках. Хотелось бы чтоб все были сделаны, но по возможности сколько...

просто логарифм - C++
Доброго времени суток! Возникла небольшая проблема: как написать функцию log(a,x), вычисляющую логарифм x по основанию a. Это нужно для...

просто вопрос=) - C++
привет всем! кто знает если сюда задачу написать за сколько минут тут могут задачу решить? скоро зачеты хотел узнать((((


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.