Форум программистов, компьютерный форум 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
09.12.2010, 23:40     Всё просто #2
Цитата Сообщение от Flaber Посмотреть сообщение
то есть где то ошибка но где??
Проще написать где не ошибка в этом алгоритме. У Вас будет выводить не только 9, но и все нечетные числа больше равные и больше 5 и равные и меньшие m.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
09.12.2010, 23:47     Всё просто #3
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>
 
bool isSimple(int a)
{
    for(int i=2; i<=a/2; ++i)
        if(a%i == 0)
            return false;
    return true;
}
 
int main()
{
     int m;
     std::cout<<"Enter m: ";
     std::cin>>m;
     int i=2;
     while(1)
     {
         if(issimple(i))
         {
            if(i > m)
               break;
            std::cout<<i<<'\n';
          }
     }
     return 0;
}
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 01:19     Всё просто #4
Действительно, просто:
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
#include <iostream>
#include <list>
 
template <typename iterator>
bool is_prime (int number, const iterator & first_known_prime, const iterator & last_known_prime) {
    for (iterator current_prime = first_known_prime; current_prime != last_known_prime; ++current_prime) {
        if (number % *current_prime == 0) return false;
        else if (*current_prime * *current_prime > number) break;
    }
    
    return true;
}
 
template <typename output_container_type>
void get_primes (int supremum, output_container_type & empty_container) {
    output_container_type primes(1, 2);
    
    for (int i = 3; i < supremum; i += 2) if (is_prime(i, primes.begin(), primes.end())) primes.push_back(i);
            
    std::swap(primes, empty_container);
}
 
int main (int argc, char * const argv[]) {
    typedef std::list<int> container_type;
    container_type primes;
 
    int supremum;
    std::cin >> supremum;
    
    get_primes(supremum, primes);
    for (container_type::const_iterator i = primes.begin(); i != primes.end(); ++i) std::cout << *i << " ";
    
    return 0;
}
Добавлено через 3 минуты
ForEveR, кстати, у тебя неправильно :p .
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 01:23     Всё просто #5
ForEveR, кстати, у тебя неправильно .
Чуть-чуть неправильно:
Цитата Сообщение от ForEveR Посмотреть сообщение
if(issimple(i))
Заменить на:
C++
1
        if(isSimple(++i))
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
10.12.2010, 01:27     Всё просто #6
volovzi, Хм. да)

Вот так верно.
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
#include <iostream>
 
bool isSimple(int a)
{
    for(int i=2; i<=a/2; ++i)
        if(a%i == 0)
            return false;
    return true;
}
 
int main()
{
     int m;
     std::cout<<"Enter m: ";
     std::cin>>m;
     int i=2;
     while(1)
     {
         if(isSimple(i))
         {
            if(i > m)
               break;
            std::cout<<i<<'\n';
         }
         ++i;
     }
     return 0;
}
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 01:42     Всё просто #7
А если серьёзно, то как-то не люблю заведомо неоптимальные функции.
Лучше уж тогда эратосфеном:
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
#include <iostream>
#include <vector>
 
int next_true (std::vector<bool> & sieve, int pos) {
    int i;
 
    for (i = pos; i < sieve.size(); ++i) if (sieve[i] == true) return i;
    
    return i;
}
 
void seed (std::vector<bool> & sieve) {
    for (int i = 2; i < sieve.size(); i = next_true(sieve, i + 1))
        for (int j = i * 2; j < sieve.size(); j += i) sieve[j] = false;
}
 
int main (int argc, char * const argv[]) {
    int supremum;
    std::cin >> supremum;
    
    std::vector<bool> sieve(supremum, true);
    sieve[0] = false;
    sieve[1] = false;
    
    seed(sieve);
    for (int i = 2; i < sieve.size(); ++i) if (sieve[i]) std::cout << i << ' ';
    
        return 0;
}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
10.12.2010, 01:43     Всё просто #8
volovzi, Булевый вектор то зачем? Нехорошо...
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 01:43     Всё просто #9
ForEveR, а что плохого?
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
10.12.2010, 01:55     Всё просто #10
Мда. Что-то я переборщил. Бредово вышло.
Про булевый вектор
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
class Primes
{
public:
    Primes(int i=2)
    {
        if(isSimple(i))
            Vec.push_back(i);
    }
 
    void push_back(int i)
    {
        if(isSimple(i))
            Vec.push_back(i);
    }
 
    bool isSimple(int i)
    {
        for(int j=2; j<=i/2; ++j)
            if(i%j == 0)
                return false;
        return true;
    }
 
    int& operator [] (size_t i)
    {
        return Vec[i];
    }
 
    const int& operator [] (size_t i) const
    {
        return Vec[i];
    }
 
    const int size() const
    {
        return Vec.size();
    }
 
    std::vector<int>::iterator begin()
    {
        return Vec.begin();
    }
 
    std::vector<int>::iterator end()
    {
        return Vec.end();
    }
 
    std::vector<int>::const_iterator begin() const
    {
        return Vec.begin();
    }
 
    std::vector<int>::const_iterator end() const
    {
        return Vec.end();
    }
private:
    std::vector<int> Vec;
};
 
std::ostream& operator <<(std::ostream& os, const Primes& Ob)
{
    std::copy(Ob.begin(), Ob.end(), std::ostream_iterator<int>(os, "\n"));
    return os;
}
 
int main()
{
    int m=0;
    std::cout<<"Enter m: ";
    std::cin>>m;
    Primes Obj;
    int i=3;
    while(1)
    {
        if(i > m)
            break;
        Obj.push_back(i++);
    }
    std::cout<<Obj;
    system("pause");
    return 0;
}
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:05     Всё просто #11
Цитата Сообщение от ForEveR Посмотреть сообщение
Мда. Что-то я переборщил. Бредово вышло.
Да, действительно, странно .

Насчёт вектора, действительно, есть такая шняга, но у меня есть оправдание, что я использую его не в обобщённом контексте, а во вполне конкретном.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
10.12.2010, 02:24     Всё просто #12
Попытка подбить 0x под это задание. Не слишком удачная.

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
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
 
int main()
{
    int m=0;
    std::cout<<"Enter m: ";
    std::cin>>m;
    int i=2;
    std::vector<int> Vec;
    try
    {
    std::generate_n(std::back_inserter(Vec), m, [&i, &m]() -> int
    {
        for(int j=2; j<=i/2; ++j)
        {
            if(i > m)
                throw 0;
            if(i%j == 0)
            {
                ++i;
                j=2;
            }
        }
        return i++;
    });
    }
    catch(...)
    {
    }
    std::vector<int>::iterator iter=std::find(Vec.begin(), Vec.end(), 0);
    if(iter != Vec.end())
    {
        std::cerr<<"Error\n";
        system("pause");
        return 1;
    }
    int t=std::distance(Vec.begin(), iter);
    Vec.resize(t);
    std::copy(Vec.begin(), Vec.end(), std::ostream_iterator<int>(std::cout, "\n"));
    system("pause");
    return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:30     Всё просто #13
Вообще-то автор темы вроде как не просил STL и не просил алгоритмы вычисления простых чисел, а просто просил показать где у него ошибка.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:33     Всё просто #14
ForEveR, ну это уже совсем жесть :jokingly: .

Добавлено через 56 секунд
valeriikozlov, дык он же сказал, что всё просто. Вот мы и развлекаемся.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:34     Всё просто #15
Цитата Сообщение от volovzi Посмотреть сообщение
Вот мы и развлекаемся.
это я заметил, можно подключится к развлечению?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:37     Всё просто #16
Нужно!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:42     Всё просто #17
Хорошо,
Если честно, то метод Эратосфена не считаю оптимальным (по объему выделяемой памяти), не помню чей метод, но считаю его оптимальней:
если заданное число не делится без остатка на все простые числа меньше его, то оно само простое число.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 03:01     Всё просто #19
Но по времени быстрее как раз алгоритм Эратосфена....
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2010, 12:01     Всё просто
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
volovzi
266 / 168 / 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.
Yandex
Объявления
10.12.2010, 12:01     Всё просто
Ответ Создать тему
Опции темы

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