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

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

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

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

09.12.2010, 21:41. Просмотров 1122. Ответов 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++
А как записать Х в кубе?

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.12.2010, 23:40     Всё просто #2
Цитата Сообщение от Flaber Посмотреть сообщение
то есть где то ошибка но где??
Проще написать где не ошибка в этом алгоритме. У Вас будет выводить не только 9, но и все нечетные числа больше равные и больше 5 и равные и меньшие m.
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 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
267 / 169 / 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++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 01:23     Всё просто #5
ForEveR, кстати, у тебя неправильно .
Чуть-чуть неправильно:
Цитата Сообщение от ForEveR Посмотреть сообщение
if(issimple(i))
Заменить на:
C++
1
        if(isSimple(++i))
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 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
267 / 169 / 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
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
10.12.2010, 01:43     Всё просто #8
volovzi, Булевый вектор то зачем? Нехорошо...
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 01:43     Всё просто #9
ForEveR, а что плохого?
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 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
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:05     Всё просто #11
Цитата Сообщение от ForEveR Посмотреть сообщение
Мда. Что-то я переборщил. Бредово вышло.
Да, действительно, странно .

Насчёт вектора, действительно, есть такая шняга, но у меня есть оправдание, что я использую его не в обобщённом контексте, а во вполне конкретном.
ForEveR
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 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++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:30     Всё просто #13
Вообще-то автор темы вроде как не просил STL и не просил алгоритмы вычисления простых чисел, а просто просил показать где у него ошибка.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
10.12.2010, 02:33     Всё просто #14
ForEveR, ну это уже совсем жесть :jokingly: .

Добавлено через 56 секунд
valeriikozlov, дык он же сказал, что всё просто. Вот мы и развлекаемся.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.12.2010, 02:34     Всё просто #15
Цитата Сообщение от volovzi Посмотреть сообщение
Вот мы и развлекаемся.
это я заметил, можно подключится к развлечению?
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
В астрале
Эксперт С++
7968 / 4730 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 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
Но по времени быстрее как раз алгоритм Эратосфена....
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.12.2010, 12:01     Всё просто
Еще ссылки по теме:

Очень просто - 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...


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

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

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