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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.82
nepster
60 / 60 / 1
Регистрация: 19.09.2009
Сообщений: 844
#1

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

08.10.2009, 21:37. Просмотров 4220. Ответов 26

Подскажите пожалуйста как при помощи цикла while и проверки вывести на экран все простые числа от 0 до 100. (1,3,5,7,11,13,17....)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2009, 21:37     Вывести все простые числа от 0 до 100 (цикл while)
Посмотрите здесь:

C++ Вывести все простые числа до n
C++ Вывести все простые делители числа
C++ Вывести на экран все простые числа
Вывести все простые числа от M до N включительно C++
C++ Цикл: Вывести все простые числа от M до N включительно
Найти все простые числа из интервала от 100 до 1000, используя логическую функцию C++
Цикл: Найти и напечатать все простые числа, меньше 100 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 13:52     Вывести все простые числа от 0 до 100 (цикл while) #21
Цитата Сообщение от 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
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.08.2011, 13:55     Вывести все простые числа от 0 до 100 (цикл while) #22
Нашел у себя быдлокод, заточенный под эту задачу
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_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:00     Вывести все простые числа от 0 до 100 (цикл while) #23
Цитата Сообщение от diagon Посмотреть сообщение
Нашел у себя быдлокод...
Просто перебор всех нечетных чисел и проверка, делится ли число на числа до своего корня там по времени не проходит =)
И почему бы вам решетом Эратосфена не воспользоваться, с таким диапазоном почти никаких расходов памяти.
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.08.2011, 14:07     Вывести все простые числа от 0 до 100 (цикл while) #24
Цитата Сообщение от Olga_ Посмотреть сообщение
почему бы вам решетом Эратосфена не воспользоваться, с таким диапазоном почти никаких расходов памяти.
Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Вышеприведенный код и то за полсекунды справляется =(
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,989
13.08.2011, 14:09     Вывести все простые числа от 0 до 100 (цикл while) #25
Цитата Сообщение от diagon Посмотреть сообщение
Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Ну я как раз им и делал. Да и первые два места вряд ли чем другим. Хотя, кто знает
Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:15     Вывести все простые числа от 0 до 100 (цикл while) #26
Цитата Сообщение от diagon Посмотреть сообщение
Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Вышеприведенный код и то за полсекунды справляется =(
В логическом массиве размера не более 1 Мб должен быстро пройти. Других более быстрых алгоритмов вроде бы нет. Здесь нет делений, одни присвоения и плюсы в цикле. Не зря диапазон от M до N задан, это неспроста

Добавлено через 2 минуты
Цитата Сообщение от grizlik78 Посмотреть сообщение
Ну я как раз им и делал. Да и первые два места вряд ли чем другим. Хотя, кто знает
Это да. Вот если бы число N было бы неограниченным таким очевидным образом, что именно алгоритм Эратосфена, то пришлось бы поломать голову
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.08.2011, 14:19     Вывести все простые числа от 0 до 100 (цикл while)
Еще ссылки по теме:

C++ Вывести все простые числа из интервала
C++ Вывести простые числа от 1 до 100
Вывести все простые числа в диапазоне от a до b C++
Вывести простые числа в пределах до 100 C++
C++ Найти все простые числа в диапазоне от 1 до 100

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,989
13.08.2011, 14:19     Вывести все простые числа от 0 до 100 (цикл while) #27
Цитата Сообщение от Olga_ Посмотреть сообщение
Других более быстрых алгоритмов вроде бы нет.
Решето Аткина должно быть более быстрым и требует меньше памяти. Но оно многократно сложнее этого незатейливого алгоритма и я пока не решился на его реализацию А уж если в рейтинг пытаться влезть, то точно не подойдёт.
Yandex
Объявления
13.08.2011, 14:19     Вывести все простые числа от 0 до 100 (цикл while)
Ответ Создать тему
Опции темы

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