Описание тега sieve-of-eratosthenes
Сито Эратосфена - это простой древний алгоритм для поиска всех простых чисел вплоть до указанного целого.
3
ответа
Найти следующий штрих с учетом всех предыдущих
Я пишу рекурсивный генератор бесконечных простых чисел, и я почти уверен, что смогу оптимизировать его лучше. Прямо сейчас, кроме таблицы поиска первых дюжин простых чисел, каждый вызов рекурсивной функции получает список всех предыдущих простых чис…
18 дек '13 в 11:51
2
ответа
Почему мое Сито Эратосфена работает так медленно?
Я пишу программу простых чисел на Python для Сита Эратосфена. Хотя это похоже на работу, но очень медленно. Как я могу ускорить это? primes = [] upperLimit = 1000 for x in range(2,upperLimit): primes.append(x) for y in range(0,int(len(primes)**0.5))…
09 окт '17 в 22:54
2
ответа
Sigsegv Ошибка при поиске простого числа в диапазоне
При решении вопроса, чтобы найти простое число в заданном диапазоне, я получаю ошибку Sigsegv, и я не могу найти, где моя ошибка и как ее исправить. #include<iostream> #include<cmath> using namespace std; int primes[10000000];// stores p…
21 апр '16 в 13:55
1
ответ
C# BitArray и Int64
Я реализую алгоритм Sieve of Eratosthenes с использованием BitArray в C# 4. Код: cPrimesB = new BitArray((int)max, true); //in constructor primes = new List<ulong>(); //in constructor //the function public ulong findPrimesBa() { ulong count = …
27 июл '11 в 12:57
2
ответа
Самый быстрый способ вычислить число до 10^18
Учитывая номер 1 <= n <= 10^18Как я могу учесть это в минимальной сложности времени? В Интернете есть много постов, посвященных тому, как вы можете найти основные факторы, но ни в одном из них (по крайней мере из того, что я видел) не говоритс…
09 май '18 в 10:48
2
ответа
Является ли Sieve of erathosthens лучшим алгоритмом для генерации простых чисел от 1 до N?
Мне задали этот вопрос в интервью. Я реализовал алгоритм, используя концепцию сита эратосфена и массив. Есть ли лучший способ обойти этот вопрос Для тех, кто не знает сита, вот ссылка: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes РЕДАКТИРОВАТЬ…
16 мар '11 в 17:20
1
ответ
Каков наилучший алгоритм для определения числа факторов первых N натуральных чисел?
Я должен найти общее количество факторов для всех чисел из 2 to N, Вот мой подход. Бежать Sieve of Eratosthenes и получить все простые числа от 2 to N, Для каждого номера из 2 to N, проведем простую факторизацию и получим показатели всех простых мно…
27 янв '19 в 20:04
2
ответа
Почему реализация этого простого сита медленнее?
Я просто немного экспериментировал с (для меня) новым языком программирования: clojure. И я написал довольно наивную "решетчатую" реализацию, которую затем попытался немного оптимизировать. Как ни странно, хотя (по крайней мере для меня), новая реал…
04 янв '11 в 11:29
1
ответ
Почему мое Сито Эратосфена дает несколько составных чисел?
Итак, после запуска моей реализации Решета Эратосфена, в некоторых случаях он также дает мне составные числа. Например. Когда предел чисел равен 10, я получаю 2, 3, 5, 7 и 9 тоже. Когда предел равен 30, я получаю 25 вместе с простыми числами. Почему…
05 авг '13 в 08:45
2
ответа
Почему моя функция не работает, когда я использую соединение?
Я пытаюсь написать функцию, которая должна вычислять все простые числа до входного параметра и возвращать его. Я делаю это для практики. Я написал эту функцию несколькими способами, но я пытался найти новые способы сделать это для большей практики и…
29 авг '18 в 17:09
1
ответ
SPOJ Проблема KPRIMES2
Я новичок в этом форуме и не очень хорошо знаю протоколы этого форума, так что простите меня за мое невежество. Мой вопрос связан с проблемой спой https://www.spoj.pl/problems/KPRIMES2/. Я получаю TIME LIMIT EXCEED для этой проблемы. Я думаю, что уз…
28 янв '11 в 05:31
1
ответ
Сито Эратосфена Время Сложность
Какова временная сложность алгоритма Сита Эратосфена для поиска простых чисел? Как рассчитать это? Пожалуйста, опишите это... Спасибо за вашу помощь!
15 фев '13 в 09:31
1
ответ
Эффективное сито эратосфена в питоне
Этот очень короткий и простой код в #Python пытается смоделировать "Сито Эратосфена" для первых N натуральных чисел с ограничениями (0) краткости сценария; (1) сведение к минимуму циклов if и for/while; (2) эффективность с точки зрения процессорного…
20 апр '18 в 07:22
2
ответа
Нужна помощь о сито эратосфена в бесплатном паскале
Мой учитель дал мне это: п<=10^6; массив из n целых чисел:ai..an(ai<=10^9); найти все простые числа. он сказал кое-что о сите из эратосфена, и я читал об этом, а также о факторизации колеса, но я все еще не мог понять, как заставить программу (fpc) …
08 окт '14 в 02:42
3
ответа
Почему мне не удается Project Euler #10?
Вопрос в том, чтобы найти сумму всех простых чисел ниже 2 миллионов. Я в значительной степени сделал вещь Sieve of Erastothenes, и программа ниже, кажется, работает для небольшого числа, то есть определите LIMIT, поскольку 10L выдает 17 как ответ. Я…
01 янв '10 в 14:49
0
ответов
Факторизация Колеса и Сито Эратосфена
Я хочу оптимизировать сито дальше. Я уже научился факторизации колес от http://en.wikipedia.org/wiki/Wheel_factorization. Но я не понимаю, как я могу реализовать факторизацию колес в сите? bool status[N]={0}; void SOE(){ status[0]=1; status[1]=1; st…
04 авг '13 в 04:34
0
ответов
Javascript Сито Эратосфена с полем ввода текста
У меня возникли некоторые проблемы с реализацией JavaScript сита Эратосфена, найденного здесь. Я знаю, что в прошлом задавались некоторые вопросы по этому поводу, но это немного над моей головой. Я скопировал скрипт с веб-страницы и добавил только т…
16 янв '14 в 18:02
0
ответов
Многопоточное сито Эратосфена - очень и очень долго
Я пытаюсь создать многопоточное сито Эратосфена Количество потоков по умолчанию установлено равным 4, хотя они могут быть указаны пользователем в качестве аргумента командной строки. Я пытаюсь пометить все интервалы простого числа в массиве одноврем…
04 мар '13 в 19:51
3
ответа
Простые числа с использованием сита эрастосфена в C
Я написал следующую программу для отображения всех простых чисел до 150. Она не выполняется вообще. что в этом плохого? # include <stdio.h> int main(void) { int p[150], i, j; for (i = 2; i < 150; i++) p[i] = 0; i = 2; while (i < 150){ if…
21 дек '12 в 01:41
3
ответа
Самый быстрый способ найти основные факторы после сита
Я сохранил все простые числа до диапазона в векторе primes после sieve, Теперь я хочу найти все основные факторы n в течение короткого времени. Мой код: i=0 while(primes[i]<=n) { if(n%primes[i]==0) { cout<<primes[i]<<endl; } while(n%p…
05 окт '15 в 15:53