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

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

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

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

09.12.2010, 21:41. Просмотров 1135. Ответов 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 секунды
то есть где то ошибка но где??
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2010, 21:41     Всё просто
Посмотрите здесь:

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:37     Всё просто #16
Нужно!
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:42     Всё просто #17
Хорошо,
Если честно, то метод Эратосфена не считаю оптимальным (по объему выделяемой памяти), не помню чей метод, но считаю его оптимальней:
если заданное число не делится без остатка на все простые числа меньше его, то оно само простое число.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 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;
}
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 03:01     Всё просто #19
Но по времени быстрее как раз алгоритм Эратосфена....
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.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 12:22     Всё просто #21
Цитата Сообщение от volovzi Посмотреть сообщение
Этот метод реализован в моём первом сообщении в этой теме.
Да точно, не заметил.
Про сравнение алгоритмов: один лучше по времени, второй по используемой памяти.

Добавлено через 2 минуты
Кстати, тот "неопознанный" алгоритм можно ускорить.
volovzi
267 / 169 / 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++
int onscreen(FILE *f) { setlocale(LC_ALL,&quot;Rus&quot;); system (&quot;cls&quot;); // очистка консоли rewind (f); // перевод указателя в начало файла...

Просто интересно - C++
#include &lt;iostream&gt; using namespace std; int main() { double z=0; double x=-2; cout&lt;&lt; x*z; system...


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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 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     Всё просто
Ответ Создать тему
Опции темы

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