Вывести простые числа в диапазоне от 2 до 1000

@Alex P · Регистрация: 18.08.2011

Author24 — интернет-сервис помощи студентам

Здраствуйте, есть задачка:

Создать программу, которая выводит на экран простые числа в диапазоне от 2 до 1000. (Число называется простым, если оно делится только на 1 и на само себя без остатка; причем числа 1 и 2 простыми не считаются).

Пробую следующим образом, но выводит все цыфры от 3 до 999

Вот как пробую я:

C

#include <iostream>
using namespace std;
void main()
 
{
    int i=3, j;
 
    while(i<1000){ 
    j=i-1; //переменная j всегда начинает считаться на 1 меньше переменной i, поскольку число может делиться на самого себя
        while (j>1) { // j>1 поскольку число может делиться на 1
            if (i%j!=0) // например 3 делим по модулю на 2 = 1.5, 5!=0 - подходит, 4%2=0 - не подходит 
            { 
                cout<<i <<' ';
            }
            j--; //уменьшаем j чтобы проделить на все числа на единицу меньше числа і и больше 1
            break;
        }
        i++;
        
    }
 
}

В чем моя ошибка, помогите плиз, заранее благодарен

@fasked · 18.08.2011, 23:55

Сообщение от grizlik78

Sieve of Atkin? Сам придумал?

Писал, чтобы решить задачку на одном из сайтов. Правда тогда мне этот метод не понадобился, но исходник вот остался.
Где-то, кстати, читал, что решето Аткина проигрывает решету Эратосфена на практике, хотя по асимптотике должно быть наоборот, но выигрыш заметен только на числах близких к 10^9.

@grizlik78 · 19.08.2011, 00:53

Сообщение от fasked

Где-то, кстати, читал, что решето Аткина проигрывает решету Эратосфена на практике, хотя по асимптотике должно быть наоборот, но выигрыш заметен только на числах близких к 10^9.

Ну при прямолинейной реализации да, но решето Аткина, позволяет экономить память, как минимум. Для Эратосфена я не представляю, как уменьшить прожорливость. В английской википедии есть ссылка на довольно неплохо оптимизированную реализацию генератора, выполненную одним из авторов алгоритма (Бернштайн).

@fasked · 19.08.2011, 02:36

Сообщение от grizlik78

Ну при прямолинейной реализации да, но решето Аткина, позволяет экономить память, как минимум. Для Эратосфена я не представляю, как уменьшить прожорливость. В английской википедии есть ссылка на довольно неплохо оптимизированную реализацию генератора, выполненную одним из авторов алгоритма (Бернштайн).

Я, на самом-то деле, понятия не имею, в какой сфере нужны такие простые числа. Я имею в виду, именно диапазоны именно небольших чисел. А генерировать диапазоны больших простых чисел... опять же зачем, да и наверное это утомительно долго

@Toshkarik · 19.08.2011, 03:19

Решение в лоб.

C++

#include <iostream>
int main()
{
    bool flag;
 
    for ( int i = 2; i <= 1000; i++ )
    {
        flag = false;
 
        for ( int j = 2; j <= i / 2 ); j++ )
        {
            if ( i % j == 0 )
            {
                flag = true;
                break;
            }
        }
 
        if ( !flag )
            std::cout << i << std::endl;
    }
 
    return 0;
}

Для небольших диапазонов. Для больших конечно лучше использовать перебор до корня.

C++

#include <iostream>
#include <cmath>
 
int main()
{
    bool flag;
 
    for ( int i = 2; i <= 1000; i++ )
    {
        flag = false;
 
        for ( int j = 2; j <= sqrt( static_cast< double > ( i ) ); j++ )
        {
            if ( i % j == 0 )
            {
                flag = true;
                break;
            }
        }
 
        if ( !flag )
            std::cout << i << std::endl;
    }
 
    return 0;
}

@Alex P · 19.08.2011, 03:50 **[ТС]**

спасибо всем за ответы/советы,

но я не могу понять таки почему ошибка в изначальном посте или следующем коде:

C

#include <iostream>
using namespace std;
void main()
 
{
        int i, j;
 
       for (i=3; i<=1000; i++) {
 
           
           for (j=i-1; j<=999, j>1; j--) { //судя по логике число нужно делить на все числа кроме его самого и 1 потому начинаем делить с числа на 1 меньше его самого до 2
               if (i%j!=0) { //проверяем условие - если число простое
               cout<<i<<' '; //выводим i
               break; //останавливаем внутренниы цыкл, переходим к внешнему, где делается i++ и все по новой
               }
           }
       }
}

Так почему же код выводит все цыфры, я только начал учить С, просьба объяснить как чайнику

Большое спасибо!

accept · 19.08.2011, 03:57

Сообщение от Alex P

просьба объяснить как чайнику

ты не знаешь, что такое простое число
прочитай определение

@grizlik78 · 19.08.2011, 04:04

Alex P, у тебя получается, что если проверяемое число не делится на какое-нибудь число, то проверяемое — простое. Но на самом деле-то наоборот: если число делится на какое-нибудь (кроме себя и единицы), то оно составное.

C++

#include <iostream>
 
using namespace std;
 
int main()
{
    int i, j;
 
    for (i=3; i<=1000; i++) {
        for (j=i-1; j>1; j--) { //судя по логике число нужно делить на все числа кроме его самого и 1 потому начинаем делить с числа на 1 меньше его самого до 2
            if (i%j==0) { //проверяем условие - если число составное
                break; //останавливаем внутренний цикл, переходим к внешнему, где делается i++ и все по новой
            }
        }
        if (1 == j)
            cout<<i<<' '; //выводим i
    }
}

@Olga_ · 19.08.2011, 09:14

Можно на маленькую капельку усовершенствовать алгоритм:

C++

#include <iostream>
 
using namespace std;
 
int main()
{
    int i, j;
 
    cout << 2 << '\n';
    for (i = 3; i <= 1000; i += 2) // проверяем только нечетные числа
    {
            j = 3;
            while (i % j && j*j <= i)   // вариант без использования функции sqrt()
               j += 2;
 
            if (j*j > i)
                cout << i << '\n';
    }
    return 0;
}

Добавлено через 15 минут
Toshkarik, вы собираетесь вызывать функцию sqrt() для одного и того же значения i столько раз, сколько шагов итерации будет совершено:

C++

1	for ( int j = 2; j <= sqrt( static_cast< double > ( i ) ); j++ )

@Toshkarik · 19.08.2011, 16:36

Сообщение от Olga_

Можно на маленькую капельку усовершенствовать алгоритм:

C++

#include <iostream>
 
using namespace std;
 
int main()
{
    int i, j;
 
    cout << 2 << '\n';
    for (i = 3; i <= 1000; i += 2) // проверяем только нечетные числа
    {
            j = 3;
            while (i % j && j*j <= i)   // вариант без использования функции sqrt()
               j += 2;
 
            if (j*j > i)
                cout << i << '\n';
    }
    return 0;
}

Добавлено через 15 минут
Toshkarik, вы собираетесь вызывать функцию sqrt() для одного и того же значения i столько раз, сколько шагов итерации будет совершено:

C++

1	for ( int j = 2; j <= sqrt( static_cast< double > ( i ) ); j++ )

Я писал на быструю руку, код не компилил. Да, можно определять корень из i всего один раз.

@fasked · 19.08.2011, 16:41

Не по теме:

Сообщение от Toshkarik

Я писал на быструю руку, код не компилил.

Не отмазывайтесь :D

@Toshkarik · 20.08.2011, 14:39

Не по теме:

Да я серьезно :) В студии бы у меня был другой немного код :) Просто я относительно недавно решал такую же задачу у Дейтлов. Вот переделал и проверил

C++

#include "stdafx.h"
 
int main()
{
    setlocale( LC_ALL, "RUS" );
 
    bool flag;
    double squart;
 
    for ( int i = 2; i <= 30000; i++ )
    {
        flag = false;
        squart = sqrt( static_cast< double > ( i ));
 
        for ( int j = 2; j <= squart; j++ )
        {
            if ( i % j == 0 )
            {
                flag = true;
                break;
            }
        }
 
        if ( !flag )
            std::cout << i << std::endl;
    }
 
    system( "PAUSE" );
    return 0;
}

@Просто лис · 20.08.2011, 16:05

Честно взято из своего самоучителя.

C++

#include <iostream>
using namespace std;
int main()
{
    int i,j;
    bool is;
    
for (i=2; i<1001; i++)
{
   is=true;
   for (j=2; j<=i/2; j++)
   if ((i%j)==0) is= false;
   if (is)
   cout <<i<<" ";
    }
    system("pause");
    return 0;
}

@Olga_ · 20.08.2011, 18:11

Сообщение от Просто лис

Честно взято из своего самоучителя...

А теперь попытайтесь данный алгоритм оптимизировать, а то пока он в крайне корявом виде, и вам тренировка.

@Просто лис · 21.08.2011, 03:15

Olga_, что оптимизировать то? У меня объём знаний языка С++, только на такую программу.

@Olga_ · 21.08.2011, 20:48

Сообщение от Просто лис

Olga_, что оптимизировать то? У меня объём знаний языка С++, только на такую программу.

Поскольку алгоритм вы взяли из книги, а алгоритм совсем не оптимальный, то можно вам попытаться его переделать. Сначала посмотрите на этот цикл

C++

1	for (j=2; j<=i/2; j++)

попробуйте усовершенствовать. Потом посмотрите на цикл с телом

C++

1 2	for (j=2; j<=i/2; j++) if ((i%j)==0) is= false;

тоже попробуйте понять почему так не очень хорошо.

@Alex P · 23.08.2011, 22:10 **[ТС]**

Всем спасибо!

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	19.08.2011, 03:57	26
	Сообщение от Alex P просьба объяснить как чайнику ты не знаешь, что такое простое число прочитай определение 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	20.08.2011, 18:11	33
	Сообщение от Просто лис Честно взято из своего самоучителя... А теперь попытайтесь данный алгоритм оптимизировать, а то пока он в крайне корявом виде, и вам тренировка. 0

@Просто лис Путешественник вселенной 189 / 160 / 119 Регистрация: 01.03.2011 Сообщений: 664
	21.08.2011, 03:15	34
	Olga_, что оптимизировать то? У меня объём знаний языка С++, только на такую программу. 0

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	18.08.2011, 23:55	21
	Сообщение от grizlik78 Sieve of Atkin? Сам придумал? Писал, чтобы решить задачку на одном из сайтов. Правда тогда мне этот метод не понадобился, но исходник вот остался. Где-то, кстати, читал, что решето Аткина проигрывает решету Эратосфена на практике, хотя по асимптотике должно быть наоборот, но выигрыш заметен только на числах близких к 10^9. 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	19.08.2011, 00:53	22
	Сообщение от fasked Где-то, кстати, читал, что решето Аткина проигрывает решету Эратосфена на практике, хотя по асимптотике должно быть наоборот, но выигрыш заметен только на числах близких к 10^9. Ну при прямолинейной реализации да, но решето Аткина, позволяет экономить память, как минимум. Для Эратосфена я не представляю, как уменьшить прожорливость. В английской википедии есть ссылка на довольно неплохо оптимизированную реализацию генератора, выполненную одним из авторов алгоритма (Бернштайн). 1

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	19.08.2011, 02:36	23
	Сообщение от grizlik78 Ну при прямолинейной реализации да, но решето Аткина, позволяет экономить память, как минимум. Для Эратосфена я не представляю, как уменьшить прожорливость. В английской википедии есть ссылка на довольно неплохо оптимизированную реализацию генератора, выполненную одним из авторов алгоритма (Бернштайн). Я, на самом-то деле, понятия не имею, в какой сфере нужны такие простые числа. Я имею в виду, именно диапазоны именно небольших чисел. А генерировать диапазоны больших простых чисел... опять же зачем, да и наверное это утомительно долго 0

@fasked
	19.08.2011, 16:41 #30
	Не по теме: Сообщение от Toshkarik Я писал на быструю руку, код не компилил. Не отмазывайтесь :D 0

@Alex P 0 / 0 / 0 Регистрация: 18.08.2011 Сообщений: 3
	23.08.2011, 22:10 [ТС]	36
	Всем спасибо! 0