С наступающим Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/12: Рейтинг темы: голосов - 12, средняя оценка - 5.00
EdHaker
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
1

Решето Эратосфена: найти все простые числа в интервале от A до B включительно

04.11.2015, 00:45. Просмотров 2119. Ответов 16
Метки нет (Все метки)

По введённым числам A и B вывести все простые числа в интервале от A до B включительно.
Входные данные
В единственной строке вводятся два числа 1 ≤ A≤ B≤ 100000.
Выходные данные
Вывести в одну строку все простые числа в интервале от A доB включительно.
Помогите пожалуйста, прилогаю код с других языков программирования, может кто сможет переделать под с++. Заранее благодарю.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
uses crt;
function prost(x:integer):boolean;
var  y:integer;
     f:boolean;
begin
x:=abs(x);
if x<2 then f:=false{0,1 не простое}
else if x=2 then f:=true{2 простое}
else if x mod 2=0 then f:=false{четные юольше 2 не простые}
else
 begin
  f:=true;
  y:=3;
  while(y*y<=x)and f do
  if x mod y=0 then f:=false
  else inc(y,2);
 end;
prost:=f
end;
var a,b,i,k:integer;
begin
repeat
writeln('Введите интервал натуральных чисел');
read(a,b);
until(a>0)and(b>a);
writeln('Простые числа в интервале [',a,',',b,']');
k:=0;
for i:=a to b do
if prost(i) then
 begin
  write(i,' ');
  inc(k)
 end;
writeln;
if k=0 then write('Нет простых чисел')
else write('Их количество=',k)
end.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
    #define N 20000
    //алгоритм "решето Эратосфена"
    unsigned int a[N];
    void main(){
       //заполним все ячейки числами по порядку: 0,1,2,3...
       for(int i=0; i<N; i++){
           a[i] = i;
       }
       //поскольку 1 не простое число, обнулим ячейку с этим числом
       a[1]=0;
       for(int s=2; s<N; s++){
           if(a[s]!=0){
               for(int j=s*2; j<N; j+=s){
                   a[j]=0;
               }
           }
       }
       for(i=0; i<N; i++){
           if(a[i]!=0){
                printf("%d\n", a[i]);
           }
       }
    }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# include <iostream>
 
using namespace std;
 
bool a[1000090];
 
int main()
{  
 
    a[0]=true;
    a[1]=true;
 
    for(long long i=2; i<=100; ++i)
    {
            if(a[i]==false)
            {
                           if(i*i<=100)
                           {
                                          for(long long j=i*i; j<=100; j+=i)
                                          {
                                                   a[j]=true;
                                          }
                           }
            }
    }
 
    for(long long i=1; i<=100; ++i)
    {
            if(a[i]==false)
            cout<<a[i]<<" ";
    }
}
Мне нужно конкретно от числа введенного с клавиатуры А до Б.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.11.2015, 00:45
Ответы с готовыми решениями:

Найти все простые числа, не превышающие число n, используя решето Эратосфена
Дано натуральное число n (n&gt;=2). Найти все простые числа, не превышающие число...

Простые числа. Решето Эратосфена
Здравствуйте! Нужна ваша помощь, не могу понять условие этой задачи: Даны...

Решето Эратосфена. По номеру простого числа найти это число
Найти n-ое по счёту простое число. Пример: 1 2 3 4 5 6 7 8 9 10 11 Из них...

Необходимо найти все простые числа в интервале
Помогите мне пожалуйста решить эти 4 задачи, мне их необходимо решить до...

Задача про простые числа. Выпишите все простые числа, находящиеся в интервале между а и б
#include &lt;stdio.h&gt; #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt;...

16
nmcf
6516 / 5745 / 2617
Регистрация: 14.04.2014
Сообщений: 24,494
04.11.2015, 10:52 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int A, B;
 
cin >> A >> B;
 
vector<bool> prime(B + 1, true);
 
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; ++i)
    if (prime[i])
        for (int j = i * i; j <= n; j += i)
            prime[j] = false;
 
for (int i = A; i <= B; ++i)
    if (prime[i])
        cout << i << endl;
0
EdHaker
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
04.11.2015, 12:13  [ТС] 3
nmcf, Как можно обойтись без vector? Решение не полное( не все тесты проходят.
0
nmcf
6516 / 5745 / 2617
Регистрация: 14.04.2014
Сообщений: 24,494
04.11.2015, 12:19 4
Какие ещё тесты? Ну замени на массив bool, и предварительно заполни его true.
0
EdHaker
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
04.11.2015, 12:52  [ТС] 5
nmcf, а можете подсказать как это конкретно сделать, у меня выдает ошибку.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;
int main() {
int A, B;
 
cin >> A >> B;
 
vector<bool> prime(B + 1, true);
 
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; ++i)
    if (prime[i])
        for (int j = i * i; j <= n; j += i)
            prime[j] = false;
 
for (int i = A; i <= B; ++i)
    if (prime[i])
        cout << i << endl;
return 0; }
пишет не описана переменная n.
0
nmcf
6516 / 5745 / 2617
Регистрация: 14.04.2014
Сообщений: 24,494
04.11.2015, 12:53 6
Замени на B.
0
EdHaker
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
04.11.2015, 12:55  [ТС] 7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
 
bool prime[10]={true};
 
prime[0] = prime[1] = false;
for (int i = 2; i * i <= 10; ++i)
    if (prime[i])
        for (int j = i * i; j <= 10; j += i)
            prime[j] = false;
 
for (int i = A; i <= B; ++i)
    if (prime[i])
        cout << i << endl;
return 0; }
- так правильно?

Добавлено через 1 минуту
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
using namespace std;
int main() {
int A, B;
 
cin >> A >> B;
 
vector<bool> prime(B + 1, true);
 
prime[0] = prime[1] = false;
for (int i = 2; i * i <= B; ++i)
    if (prime[i])
        for (int j = i * i; j <= B; j += i)
            prime[j] = false;
 
for (int i = A; i <= B; ++i)
    if (prime[i])
        cout << i << endl;
return 0; }
- так работает только половина тестов, п.с на сайте с олимпиадными заданиями. Вот ссылка на него, если что http://www.e-olymp.com/ru/problems/4739 .
0
Dimension
Dimension
574 / 444 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
04.11.2015, 13:15 8
неужели так сложно найти в интернете реализацию и добавить ограничения на от А до Б
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int a, b;
const int N = 100001;
int lp[N + 1];
vector<int> pr;
int main() {
    cin >> a >> b;
    for (int i = 2; i <= b; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr.push_back(i);
        }
        for (int j = 0; j<(int)pr.size() && pr[j] <= lp[i] && i*pr[j] <= b; ++j)
            lp[i * pr[j]] = pr[j];
    }
    for (auto i : pr)
        if (i >= a&&i <= b)
            cout << i << " ";
    cin.get(), cin.get();
    return 0;
}
0
_Ivana
3237 / 1870 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
04.11.2015, 13:46 9
На сайте написано прямым текстом про решето Эратосфена, а мне больше нравится через гипотезу Бертрана искать. Тоже все тесты проходит, и быстрее получается.
0
nmcf
6516 / 5745 / 2617
Регистрация: 14.04.2014
Сообщений: 24,494
04.11.2015, 15:02 10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int A, B;
 
cin >> A >> B;
 
bool *prime = new bool[B + 1];
fill(prime + 2, prime + B + 1, true);
 
prime[0] = prime[1] = false;
for (int i = 2; i * i <= B; ++i)
    if (prime[i])
        for (int j = i * i; j <= B; j += i)
            prime[j] = false;
 
for (int i = A; i <= B; ++i)
    if (prime[i])
        cout << i << endl;
 
delete[] prime;
Подключить <algorithm>.
0
Dimension
Dimension
574 / 444 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
04.11.2015, 15:06 11
Цитата Сообщение от _Ivana Посмотреть сообщение
гипотезу Бертрана
за сколько работает ?(время ,память)
0
EdHaker
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
04.11.2015, 15:09  [ТС] 12
Dimension, Спасибо работает, а как переделать под обычные массивы? Без использования vector.

Добавлено через 1 минуту
А то я не совсем понимаю , как это использовать( и мой уровень программирования ниже, чем написан.
0
_Ivana
3237 / 1870 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
04.11.2015, 15:20 13
Да секунды 4 считает, да.... А Бертран 0. Но может я Эратосфена неоптимально накостылил, но после Бертрана мне его и довелосипедивать не хочется даже. Хотя можно попробовать выжать оптимум.
Haskell
1
2
3
4
5
6
7
8
9
10
primesBert = 2 : filter isprime [3,5..] where
    isprime n = all ((/=0).(mod n)) $ takeWhile ((<=n).(^2)) primesBert
 
primesErat = sieve $ 2:[3,5..] where
    sieve (s:ss) = s : (filter ((/=0).(`mod` s)) $ sieve ss)
 
main = do
    let n = 2000
    print $ primesBert !! n
    print $ primesErat !! n
https://ideone.com/rS0Qhi
0
Dimension
Dimension
574 / 444 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
04.11.2015, 15:33 14
Лучший ответ Сообщение было отмечено EdHaker как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
int a, b;
const int N = 100001;
int lp[N + 1];
int pr[N+1],e;
int main() {
    cin >> a >> b;
    for (int i = 2; i <= b; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            pr[e++]=i;
        }
        for (int j = 0; j<(int)e && pr[j] <= lp[i] && i*pr[j] <= b; ++j)
            lp[i * pr[j]] = pr[j];
    }
    for (int i=0;i<=e;i++)
        if (pr[i] >= a&&pr[i] <= b)
            cout << pr[i] << " ";
    cin.get(), cin.get();
    return 0;
}
Добавлено через 11 минут
Цитата Сообщение от _Ivana Посмотреть сообщение
Да секунды 4 считает
у вас явно что-то не правильно ,У меня за 0с считает ,если искать все простые до 100к ,и за 0.01 если до 1млн
https://ideone.com/8LFRFN
1
_Ivana
3237 / 1870 / 235
Регистрация: 01.03.2013
Сообщений: 5,111
Записей в блоге: 5
04.11.2015, 15:39 15
Неудивительно, на Сях, да через заранее нарезанные статические глобальные массивы Я про сравнение алгоритмов имею в виду - Бертран имхо менее затратный (если не ошибаюсь).
0
EdHaker
1 / 1 / 0
Регистрация: 23.09.2015
Сообщений: 100
04.11.2015, 15:43  [ТС] 16
Dimension, спасибо большое, а не могли бы вы если не затруднит дать еще хоть какое-то объяснение к коду?
0
Dimension
Dimension
574 / 444 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
04.11.2015, 15:48 17
осталось только отнести этот код вашему преподавателю и получить за вас зачет,да?
0
04.11.2015, 15:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2015, 15:48

Вывести все простые числа от M до N включительно
Вывести все простые числа от M до N включительно. Ввод В первой строке...

Вывести все простые числа от M до N включительно
Ребят, как можно сократить время выполнения этой задачи. Необходимо вывести...

Цикл: Вывести все простые числа от M до N включительно
Вывести все простые числа от M до N включительно. Вывести числа в порядке...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru