VPF::помогите изменить программу, нужно чтобы она

anatox91

Дата 18.1.2008, 21:50 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: 1
Всего: 13

у меня есть программа, которая определяет вводимое число на простоту:

Код


#include <iostream>
#include <math.h>
using namespace std;
int main() {
    int n;         // Проверяемое число
    int i;         //Счетчик циклов
    bool is_prime;  //Булев флаг
    //Предположим, что число n вляется простым,
    // пока не докажем обратное
    is_prime=true;

    //Считать число с клавиатуры
    
    cout << "Enter a number and press ENTER: ";
    cin >> n;
    cin.ignore();
    
    //Проверка числа, выполняя проверку делимости
    //на все целые числа от 2 to sqrt(n).
    
    i = 2;
    double sqrt_n = sqrt(static_cast<double>(n));
    while (i <= sqrt_n) {
          //Пока значение переменной i <= sqrt(n),
          if (n % i == 0) { //Если значение переменной
                           //случайно делится на n,
          is_prime = false;  //n не является
          break;             //простым числом.
          }
          i++;               //Прибавить один к значению
                             //переменной i.
          }
          
          //Print results
          
          if (is_prime)
                cout << "Number is prime.";
          else
                cout << "Number is not prime.";
          cin.get();
          return 0;
}

помогите пожалуйста сделать так, чтобы программа сразу вывела все простые числа от 1 до 100 smile

Это сообщение отредактировал(а) anatox91 - 18.1.2008, 21:54

--------------------

The code is the design ©

Sony VAIO VGN-FW480J

user posted image

JackYF

Дата 18.1.2008, 22:01 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 6
Всего: 162

Цитата(anatox91 @ 18.1.2008, 20:50

)

чтобы программа сразу вывела все простые числа от 1 до 100

выдели проверку на простоту в отдельную функцию, а затем в main() вызывай её в цикле.

--------------------

Пожаловаться на меня как модератора можно здесь.

anatox91

Дата 18.1.2008, 22:13 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: 1
Всего: 13

JackYF, я тоже так с самого начала собирался сделать, только запутался с составными инструкциями, и не могу сделать так, чтобы после проверки бралось следующее число, т.е. n++, и снова проверялось, а если простое - то на вывод... smile

был бы очень благодарен, если бы кто-нибудь помог smile

Это сообщение отредактировал(а) anatox91 - 18.1.2008, 22:15

--------------------

The code is the design ©

Sony VAIO VGN-FW480J

user posted image

Prof_2000

Дата 18.1.2008, 22:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 121
Регистрация: 26.3.2005
Где: Харьков, Украина

Репутация: нет
Всего: 1

Цитата

выдели проверку на простоту в отдельную функцию, а затем в main() вызывай её в цикле.

Вообще-то, это самая распространенная ошибка при создании такой программы... По крайней мере, если нужно оптимизированное решение. В таком случае, нужно хранить стек уже найденных простых чисел и при проверке делить ТОЛЬКО на них.

Ну а если нужно только узкоспециализированное решение - то почему бы не сделать

Код


printf("2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101")

--------------------

Pereant qui ante nos nostra dixerunt! (лат.) Да погибнут те, кто раньше нас высказал наши мысли!

JackYF

Дата 18.1.2008, 22:32 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 6
Всего: 162

Цитата(Prof_2000 @ 18.1.2008, 21:26

)

printf("2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101")

Цитата(Prof_2000 @ 18.1.2008, 21:26

)

По крайней мере, если нужно оптимизированное решение.

Оптимизированное решение нужно тогда, когда есть хоть какое-то.
Название раздела прочитай smile

Вот набросок неоптимизированного варианта:

Код


#include <iostream>
#include <cmath>
using namespace std;

bool isPrime (unsigned int n)
{
    //Проверка числа, выполняя проверку делимости
    //на все целые числа от 2 to sqrt(n).
    bool is_prime = true;
    i = 2;
    double sqrt_n = sqrt(static_cast<double>(n));
    while (i <= sqrt_n) {
          //Пока значение переменной i <= sqrt(n),
          if (n % i == 0) { //Если значение переменной
                           //случайно делится на n,
          is_prime = false;  //n не является
          break;             //простым числом.
          }
          i++;               //Прибавить один к значению
                             //переменной i.
          }
}

int main()
{
  for (unsigned int i = 0; i <= 100; ++i)
  {
      if (isPrime(i))
                cout << "Number is prime.";
          else
                cout << "Number is not prime.";
  }        
  return 0;
}

--------------------

Пожаловаться на меня как модератора можно здесь.

anatox91

Дата 18.1.2008, 22:35 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: 1
Всего: 13

Цитата

почему бы не сделать

Код


printf("2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101")

Prof_2000, это-то всегда можно сделать, а мне стало интересно сделать именно программу, которая сама это вычисляет... это задачка из книги Г.Шилдта - С++. Руководство для начинающих

Это сообщение отредактировал(а) anatox91 - 18.1.2008, 22:36

--------------------

The code is the design ©

Sony VAIO VGN-FW480J

user posted image

Prof_2000

Дата 18.1.2008, 22:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 121
Регистрация: 26.3.2005
Где: Харьков, Украина

Репутация: нет
Всего: 1

Ну тогда вот код одновременно и интересный, и неплохой по производительности:

Код


#include <deque>
#include <iostream>
#include <math.h>

using namespace std;

#define MAX_VAL 100

// Алгоритм: начинаем с числа 2. Выводим текущее число, "вычеркиваем" числа, кратные текущему, ищем следующее невычеркнутое число.
void main (void)
{
    int min_val, max_val;
    cout << "Enter left limit: ";
    cin >> min_val;
    cout << "Enter right limit: ";
    cin >> max_val;
    if (max_val > MAX_VAL || min_val < 2 || max_val < min_val)
    {
        cout << "Wrong limits";
        return;
    };
    // Поиск простых ведем до корня из max_val
    int sqrt_max_val = (int)sqrt((double)max_val);
    // Признаки "вычеркнутости" чисел (элементы 0 и 1 не используются)
    deque<bool> flags (max_val+1, false);  // первоначально все числа не перечеркнуты
    int current_value (2);
    do
    {
        if (current_value >= min_val)
            cout << current_value << endl;
        // Вычеркиваем все числа, кратные current_value, начиная с его квадрата
        for (int i = current_value * current_value; i <= max_val; i += current_value)
            flags[i] = true;
        // Ищем следующее невычеркнутое число
        for (++current_value; current_value <= sqrt_max_val && flags[current_value]; ++current_value) ;
    } while (current_value <= sqrt_max_val);
    // Выведем все невычеркнутые числа больше корня из N, при этом не рассматриваем числа менее min_val
    for (current_value = min_val > sqrt_max_val+1 ? min_val : sqrt_max_val+1; current_value <= max_val; ++current_value)
        if (!flags[current_value])
            cout << current_value << endl;
};

(слизано с forum.codenet.ru) smile

--------------------

Pereant qui ante nos nostra dixerunt! (лат.) Да погибнут те, кто раньше нас высказал наши мысли!

W4FhLF

Дата 18.1.2008, 22:50 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 2
Всего: 121

Prof_2000, этот алгоритм называется Решето Эратосфена

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

susanin

Дата 18.1.2008, 22:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 587
Регистрация: 7.10.2006
Где: Санкт-Петербург

Репутация: 2
Всего: 7

anatox91, хотел бы предложить свой вариант решения пробемы..

Код


#include <iostream>
using namespace std;

bool easy(int);
int main()
{
    for(int i=1;i<101;i++)
    cout<<boolalpha<<easy(i)<<endl;
    
    return 0;
}
bool easy(int a)
{
    for(int i=2;i<a;i++)
    {
        if(a%i==0)
            return false;
    }
    return true;
}

пойдет?

anatox91

Дата 18.1.2008, 22:58 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: 1
Всего: 13

Prof_2000, компилятор почему-то находит ошибки...
W4FhLF, а вот этот алгоритм очень интересный, наверно попробую завтра через него решить
susanin, вот что-то типа такого я и хотел сделать, правда после компиляции (ошибок не было) просто пустое окошко выходит...

спасибо всем откликнувшимся!

Это сообщение отредактировал(а) anatox91 - 18.1.2008, 23:02

--------------------

The code is the design ©

Sony VAIO VGN-FW480J

user posted image

Prof_2000

Дата 18.1.2008, 23:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 121
Регистрация: 26.3.2005
Где: Харьков, Украина

Репутация: нет
Всего: 1

Цитата

W4FhLF, а вот этот алгоритм очень интересный, наверно попробую завтра через него решить

Вообще-то, W4FhLF отметил, что приведенный мной алгоритм называется решетом Эратосфена.

Никогда не знал названий этих алгоритмов. smile

А их, еще, оказывается, весьма много...

Сам всё время писал на Делфи. Чаще всего реализовывал(как только что, после прочтения, оказалось) Решето Сундарама.
Хотя и до этого алгоритма додумывался... Подумать только - а ведь его Эратосфен еще во 2м в.до н.э. придумал smile

anatox91, а что за ошибки? У меня gcc нормально скомпилировала.

--------------------

Pereant qui ante nos nostra dixerunt! (лат.) Да погибнут те, кто раньше нас высказал наши мысли!

anatox91

Дата 18.1.2008, 23:18 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: 1
Всего: 13

Prof_2000, просто я в приведенном тобою коде не все понял, т.к. я еще в самом начале изучения С++, а алгоритм мне понравился smile

а ошибки вот какие выводит:
'main' must return 'int'
In function 'int main(...)':
return-statement with no value, int function returning 'int'
хотя у меня еще может быть как-то неправильно настроен компилятор (тоже gcc, среда Dev-C++), я в его настройках особо не копался еще smile

--------------------

Sony VAIO VGN-FW480J

user posted image

Prof_2000

Дата 18.1.2008, 23:21 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 121
Регистрация: 26.3.2005
Где: Харьков, Украина

Репутация: нет
Всего: 1

Напиши вместо

Код


void main(void)

Код


int main(void)

и в конце допиши return 0;

--------------------

Pereant qui ante nos nostra dixerunt! (лат.) Да погибнут те, кто раньше нас высказал наши мысли!

susanin

Дата 18.1.2008, 23:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 587
Регистрация: 7.10.2006
Где: Санкт-Петербург

Репутация: 2
Всего: 7

anatox91, а что мешает взять мой код, и сравнив со своим найти у себя ошибки?=)

anatox91

Дата 18.1.2008, 23:25 (ссылка)

(нет голосов)

Загрузка ...

программист-самоучка

Профиль
Группа: Участник
Сообщений: 699
Регистрация: 12.1.2008
Где: ++Украина.Крым++

Репутация: 1
Всего: 13

Prof_2000, пробовал, еще до того как ты написал, только после ввода обоих значений программа сразу закрывается... smile

susanin, попробую smile

, только завтра, сейчас уже времени нет smile

Это сообщение отредактировал(а) anatox91 - 18.1.2008, 23:29

--------------------

Sony VAIO VGN-FW480J

user posted image

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »