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

Простые числа - C++

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

Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p. C++
C++ Даны целые числа р и q. Получить все делители числа q, взаимно простые с р
Даны целые числа р и q. Получить все делители числа q, взаимно простые с р. C++
C++ Даны натуральные числа a,b(a<= Ь). Получить все простые числа р, удовлетворяющие неравенствам a<= р<= b.
C++ Найти все трехзначные простые числа. Определить функцию позволяющую распознавать простые числа
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 13:52     Простые числа #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
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.08.2011, 13:55     Простые числа #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_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:00     Простые числа #23
Цитата Сообщение от diagon Посмотреть сообщение
Нашел у себя быдлокод...
Просто перебор всех нечетных чисел и проверка, делится ли число на числа до своего корня там по времени не проходит =)
И почему бы вам решетом Эратосфена не воспользоваться, с таким диапазоном почти никаких расходов памяти.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.08.2011, 14:07     Простые числа #24
Цитата Сообщение от Olga_ Посмотреть сообщение
почему бы вам решетом Эратосфена не воспользоваться, с таким диапазоном почти никаких расходов памяти.
Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Вышеприведенный код и то за полсекунды справляется =(
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.08.2011, 14:09     Простые числа #25
Цитата Сообщение от diagon Посмотреть сообщение
Я тогда о нем не знал, да и пройдет он разве...
Там же O(nloglogn), а числа надо до 10^6 перебрать менее чем за секунду.
Ну я как раз им и делал. Да и первые два места вряд ли чем другим. Хотя, кто знает
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
13.08.2011, 14:15     Простые числа #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     Простые числа
Еще ссылки по теме:

C++ Одномерный массив. Вывести на экран все числа, индексы которых есть простые числа.
C++ Дано натуральное число. Вывести на экран все простые числа до заданного числа.
Даны натуральные числа p и q. Получить все делители числа q, взаимно простые к p C++

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
13.08.2011, 14:19     Простые числа #27
Цитата Сообщение от Olga_ Посмотреть сообщение
Других более быстрых алгоритмов вроде бы нет.
Решето Аткина должно быть более быстрым и требует меньше памяти. Но оно многократно сложнее этого незатейливого алгоритма и я пока не решился на его реализацию А уж если в рейтинг пытаться влезть, то точно не подойдёт.
Yandex
Объявления
13.08.2011, 14:19     Простые числа
Ответ Создать тему

Метки
решето эратосфена
Опции темы

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