0 / 0 / 1
Регистрация: 07.12.2015
Сообщений: 33
1

Решето Эратосфена. Как ускорить?

09.12.2015, 09:44. Показов 1601. Ответов 10
Метки нет (Все метки)

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

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
33
34
35
36
#include <bits/stdc++.h>
 
using namespace std;
 
int prime(int a)
{
    if (a == 2)
        return 1;
    for (int i = 2; i * i <= a; ++i)
    {
        if (a % i == 0)
        {
            return 0;
        }
    } 
    return 1; 
}
int n, m, c;
 
int main()
{
    cin >> n >> m;
    for (int i = n; i <= m; ++i)
    {
        if (prime(i))
        {
            cout << i << " ";
            c++;
        }
    }
    if (c == 0)
    {
        cout << "Absent";
    }
    return 0;
}
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.12.2015, 09:44
Ответы с готовыми решениями:

Решето Эратосфена (сегмент): медленно работает - как можно ускорить?
Подсчёт числа простых чисел в диапазоне от &quot;from&quot; до &quot;to&quot; typedef UINT64 Number; __device__...

Как разложить число на простые множители, используя решето Эратосфена?
Я только код для решета Эратосфена знаю(

Решето Эратосфена
Дано число N (2&lt;=N &lt;=10000), найдите и выведите простые числа между 2 и данным N. Простое число -...

Решето Эратосфена
Возможно ли найти простые числа методом решета Эратосфена с помощью вектора за один проход? ...

10
Эксперт C
25992 / 16199 / 3476
Регистрация: 24.12.2010
Сообщений: 35,450
09.12.2015, 11:07 2
Цитата Сообщение от Zadr Посмотреть сообщение
как ускорить.
C++
1
2
3
4
5
6
7
8
int prime(int a)
{
if (a == 2) return 1;
if (a==1 || a%2==0) return 0;
for (int i = 3; i * i <= a; i+=2) 
  if (a % i == 0)  return 0;
return 1; 
}
Добавлено через 5 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{ int n, m, i, c=0;
cin >> n >> m;
if (n==1) n++;
if (n==2 && n<=m) {
  cout << "2  ";
  n++;
  c++;
}
if (n%2==0) n++;
for (int i = n; i <= m; i+=2)
  if (prime(i)) {
    cout << i << " ";
    c++;
  } 
if (c == 0)
  cout << "Absent";
return 0;
}
1
Модератор
Эксперт по электронике
8478 / 6305 / 854
Регистрация: 14.02.2011
Сообщений: 21,855
09.12.2015, 11:14 3
Цитата Сообщение от Байт Посмотреть сообщение
for (int i = 3; i * i <= a; i+=2)
при каждой итерации умножение
может один раз корень взять
C++
1
2
3
int tmp=sqrt(a);
for (int i = 3; i <= tmp; i+=2) 
  if (a % i == 0)  return 0;
а вообще тема не раз обсуждалась
Быстрая проверка натурального числа на простоту
и тобой тоже
Цитата Сообщение от Zadr Посмотреть сообщение
C++
1
2
3
4
5
6
int prime(int a)
{
 if (a == 2)
  return 1;
  for (int i = 2; i * i <= a; ++i)
  {
и причем здесь решето Эратосфена ?
1
0 / 0 / 0
Регистрация: 13.04.2018
Сообщений: 23
12.08.2019, 19:03 4
Самый быстрое решето эратосфена
Python
1
2
3
n = int(input("Введите число до которго надо, найти простые числа - "))
s = [x for x in range(2, n) if x not in [i for sub in[list(range(2 * j, n, j)) for j in range(2, n // 2)] for i in sub]]
print(*s)
0
609 / 414 / 151
Регистрация: 11.01.2019
Сообщений: 1,736
12.08.2019, 22:16 5
Решето Аткина асимптотически быстрее Эратосфена.
0
Don't worry, be happy
17149 / 10032 / 1933
Регистрация: 27.09.2012
Сообщений: 24,973
Записей в блоге: 1
12.08.2019, 22:26 6
karochTOSHA, через 4 года ты решил написать решение в разделе C++ не на C++?
Браво! Рекорд побит.
0
Эксперт C
25992 / 16199 / 3476
Регистрация: 24.12.2010
Сообщений: 35,450
13.08.2019, 09:18 7

Не по теме:

Croessmah, И все-таки мне никак не понять такого презрительного отношения к "некропостам". Как будто у форума только одна задача - дать ответ страждущему ТС-у! Имхо, это не совсем так



Добавлено через 6 минут
Цитата Сообщение от ValeryS Посмотреть сообщение
и причем здесь решето Эратосфена ?
В самом деле - при чем? Представленные здесь коды просто определяют и выводят простые числа. Решето - это совсем другой метод. И он быстрее. Но требует дополнительной памяти.
0
Croessmah
13.08.2019, 13:53
  #8

Не по теме:

Цитата Сообщение от Байт Посмотреть сообщение
И все-таки мне никак не понять такого презрительного отношения к "некропостам"
В подавляющем большинстве случаев, как и в данном, они бесполезны.

0
Байт
13.08.2019, 21:56
  #9

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
они бесполезны
Каковы ваши критерии пользы?

0
Croessmah
13.08.2019, 22:50
  #10

Не по теме:

Цитата Сообщение от Байт Посмотреть сообщение
Каковы ваши критерии пользы?
Хотя бы, чтобы раздел верный был. Это уже достижение для многих.

0
Байт
14.08.2019, 09:46     Решето Эратосфена. Как ускорить?
  #11

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
чтобы раздел верный был
Да, верно. С разделами частенько ерунда получается. И, не считая случаев явного головотяпства, это не всегда вина ТС-ов.
У меня есть некоторые соображения на этот счет. Но для них есть тут специальный топик. Вот соберусь с духом, и все там выложу. И там это, конечно, уже не будет оффтопом.

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.08.2019, 09:46

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Решето Эратосфена
Простое число — это любое целое число, которое точно делится без остатка только само на себя и на...

Решето Эратосфена
В решете эратосфена из книги в условии есть непонятная вещь: if (i * 1ll * i &lt;= n) - возле единицы...

Решето Эратосфена
Написать функция для выполнения алгоритма решить Эратосфена! зарания спасибо!!!

Решето Эратосфена
Подскажите реализацию (код) метода шифрования - решета Эратосфена, пожалуйста.


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

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

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