Вывести все простые числа от 0 до 100 (цикл while)

@nepster · Регистрация: 19.09.2009

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

Подскажите пожалуйста как при помощи цикла while и проверки вывести на экран все простые числа от 0 до 100. (1,3,5,7,11,13,17....)

@Olga_ · 13.08.2011, 13:52

Сообщение от x-positive

Как вариант введу свой код, может кому-то пригодится:
(код готовой программы, которая выводит все простые числа, меньше чем число N)

C++
1
2
3
#include <stdio.h>
while (X<N)
   for (I = 2; I < X; I++) if (!(X % I)) Z = 0;

С таким внутренним циклом for это как идти в магазин за хлебом и каждый дом, стоящий на пути, по 10 раз вокруг обходить, а то и больше

@diagon · 13.08.2011, 13:55

Нашел у себя быдлокод, заточенный под эту задачу

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <fstream>
#include <cmath>
int p[99999], k, i = 3, f, s, j, c, q, x;
main(){
    std::fstream("input.txt") >> f >> s;
    std::ofstream o("output.txt");
    if (f == 2) { o << 2 << ' '; c = 1; }
    for (; i <= s; i+=2){
        x = 1;
        for (j = 0, q = sqrt(1. * i); j < k && p[j] <= q; )
            if (i % p[j++] == 0) {x = 0; break;}
        if (x) {
            p[k++] = i; 
            if ( i >= f) {o << i << ' '; c = 1;}
        }
    }
    if (!c) o << "Absent"; 
}

Просто перебор всех нечетных чисел и проверка, делится ли число на числа до своего корня там по времени не проходит =)

@Olga_ · 13.08.2011, 14:00

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

Нашел у себя быдлокод...
Просто перебор всех нечетных чисел и проверка, делится ли число на числа до своего корня там по времени не проходит =)

И почему бы вам решетом Эратосфена не воспользоваться, с таким диапазоном почти никаких расходов памяти.

@diagon · 13.08.2011, 14:07

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

почему бы вам решетом Эратосфена не воспользоваться, с таким диапазоном почти никаких расходов памяти.

Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Вышеприведенный код и то за полсекунды справляется =(

@grizlik78 · 13.08.2011, 14:09

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

Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.

Ну я как раз им и делал. Да и первые два места вряд ли чем другим. Хотя, кто знает

@Olga_ · 13.08.2011, 14:15

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

Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Вышеприведенный код и то за полсекунды справляется =(

В логическом массиве размера не более 1 Мб должен быстро пройти. Других более быстрых алгоритмов вроде бы нет. Здесь нет делений, одни присвоения и плюсы в цикле. Не зря диапазон от M до N задан, это неспроста

Добавлено через 2 минуты

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

Ну я как раз им и делал. Да и первые два места вряд ли чем другим. Хотя, кто знает

Это да. Вот если бы число N было бы неограниченным таким очевидным образом, что именно алгоритм Эратосфена, то пришлось бы поломать голову

@grizlik78 · 13.08.2011, 14:19

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

Других более быстрых алгоритмов вроде бы нет.

Решето Аткина должно быть более быстрым и требует меньше памяти. Но оно многократно сложнее этого незатейливого алгоритма и я пока не решился на его реализацию

А уж если в рейтинг пытаться влезть, то точно не подойдёт.

Новые блоги и статьи Все статьи Все блоги /
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

@nepster 61 / 61 / 11 Регистрация: 19.09.2009 Сообщений: 844

	Вывести все простые числа от 0 до 100 (цикл while) 08.10.2009, 21:37. Показов 24961. Ответов 26 Метки решето эратосфена (Все метки) Подскажите пожалуйста как при помощи цикла while и проверки вывести на экран все простые числа от 0 до 100. (1,3,5,7,11,13,17....) 0