Публикации по теме 'sieve-of-eratosthenes'
Алгоритм решета Эратосфена в Java
здесь мы собираемся понять, как найти простые числа от 1 до n с помощью java
во-первых, мы собираемся понять концептуальную часть этого алгоритма, после этого мы будем искать кодирующую область решета Эратосфена, хорошо.
отлично, прежде всего у нас должен возникнуть вопрос, зачем использовать этот алгоритм?
вот ответ: решето Эратосфена — один из самых эффективных способов найти все простые числа, меньшие n, когда n меньше 10 миллионов. Временная сложность этого алгоритма составляет..
Вопросы по теме 'sieve-of-eratosthenes'
Решето Эратосфена в Хаскелле
Я решаю некоторые классические задачи на Haskell, чтобы развить свои функциональные навыки, и у меня есть проблема с реализацией оптимизации, предложенной на этом "Практика программирования" сайт:
У меня есть три решения этой проблемы, и третье...
2867 просмотров
schedule
21.06.2022
Scala: повторять последовательность при ее изменении?
Я пытаюсь реализовать Решето Эратосфена в Scala.
Я начинаю с инициализации последовательности всех нечетных чисел плюс 2:
// (end goal is to find all prime factors of bigNumber)
val largestPrime : Long =...
8076 просмотров
schedule
14.11.2022
Алгоритм простого числа
Может ли кто-нибудь сказать мне, как реализовать алгоритм Сито Эратосфена на C? Мне нужно сгенерировать простые числа, но мой алгоритм медленный.
Мой код:
#include <stdio.h>
int prime(long int i)
{
long int j;
int state = 1;...
25911 просмотров
schedule
23.03.2022
SPOJ Задача KPRIMES2
Я новичок на этом форуме и не очень хорошо знаком с протоколами этого форума, так что извините меня за мое невежество. Мой вопрос связан с проблемой spoj https://www.spoj.pl/problems/KPRIMES2/ . Я получаю ПРЕВЫШЕНИЕ ВРЕМЕНИ для этой проблемы. Я...
1179 просмотров
schedule
09.06.2022
Сумма простых чисел меньше двух миллионов. Сито Эратосфена
Возникли небольшие проблемы с решением задачи: «Вычислите сумму простых чисел меньше двух миллионов». Я использую метод «Решета Эратосфена». Мой метод отлично работает для нахождения простых чисел до сотни, но когда я пытаюсь найти сумму простых...
2767 просмотров
schedule
22.05.2022
Дальнейшее ускорение метода сита Эратосфена для нахождения простых чисел
Я видел этот c-код использования метода Sieve Эратосфена для поиска простых чисел, но я не могу расширить это еще больше целых чисел (например, до 1000000000 и даже больше) из-за потребления памяти для выделения такого большого массива char....
919 просмотров
schedule
29.12.2022
Оптимизация алгоритма решета Эратосфена Python
Я пытаюсь реализовать Решето Эратосфена. Вывод кажется правильным (минус «2», которое необходимо добавить), но если входные данные функции больше 100 КБ или около того, это, по-видимому, займет слишком много времени. Как я могу оптимизировать эту...
2747 просмотров
schedule
05.10.2022
Сегментированное решето Эратосфена?
Сделать простое сито достаточно просто:
for (int i=2; i<=N; i++){
if (sieve[i]==0){
cout << i << " is prime" << endl;
for (int j = i; j<=N; j+=i){
sieve[j]=1;
}
}
cout...
30867 просмотров
schedule
26.03.2022
Возможно ли сегментированное решето Аткина?
Мне известно о том, что решето Эратосфена можно реализовать так, чтобы оно находило простые числа непрерывно без верхней границы (сегментированное решето).
У меня вопрос: можно ли таким же образом реализовать решето Аткина / Бернштейна?...
1029 просмотров
schedule
04.04.2022
Программа для поиска всех простых чисел в очень большом заданном диапазоне целых чисел
Я столкнулся со следующим вопросом на веб-сайте программирования: Питер хочет сгенерировать несколько простых чисел для своей криптосистемы. Помоги ему! Ваша задача - сгенерировать все простые числа между двумя заданными числами!
Вход
Ввод...
6380 просмотров
schedule
18.04.2022
SPOJ PRIME1 : TLE
Я попытался реализовать алгоритм сегментированного сита для этого [вопроса]: http://www.spoj.pl/problems/PRIME1/ следующим образом:
#include <iostream>
#include <string>
#include <set>
#include<math.h>...
2202 просмотров
schedule
20.11.2022
Какова идеальная реализация решета Эратосфена между списками, массивами и изменяемыми массивами?
В Haskell я нашел три простые реализации решета Эратосфена на странице Rosetta Code .
Теперь мой вопрос: какой из них следует использовать в каких ситуациях?
Было бы полезно исправить мои первоначальные рассуждения:
Я предполагаю, что...
1679 просмотров
schedule
09.06.2022
Как я могу заблокировать потоки до тех пор, пока не будет найдено основное число, разблокировать его, а затем заставить их ждать до следующего простого числа?
Я пишу многопоточное решето Эратосфена, где мне приходится использовать pthreads. Я почти уверен, что это можно сделать с помощью мьютексов и cond_waits. Я создаю 4 потока в начале программы, а затем заставляю их ждать, пока Решето Эратосфена не...
352 просмотров
schedule
23.05.2023
Ошибка сегментации с алгоритмом решет Эратосфена в C
Итак, эта функция, которую я создал, использует алгоритм решета Эратосфена для вычисления всех простых чисел ‹= n. Эта функция сохраняет простые числа и количество простых чисел в параметрах.
Когда функция завершается, простые числа должны...
316 просмотров
schedule
15.01.2023
Быстрое сито простых чисел в Python
Я проходил генерацию простых чисел в python, используя сито Эратосфена и решения, которые люди рекламируют как относительно быстрый вариант, например, в нескольких из ответы на вопрос об оптимизации генерации простых чисел в python не являются...
17893 просмотров
schedule
25.08.2022
Решето Эратосфена с использованием битового массива
У меня есть битовый массив prime[] of unsigned int . Я хочу реализовать решето Эратосфена, используя этот массив, чтобы каждый бит представлял число n . То есть, учитывая n , элемент массива, который содержит бит, соответствующий n , будет...
766 просмотров
schedule
12.12.2022
Почему мой код Ruby для Project Euler #10 такой медленный?
Я относительно новичок в Ruby, но с точки зрения языка он кажется достаточно простым. Я работаю над проектом Euler с Ruby, и у меня огромная проблема со скоростью в следующем:
Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17. Найдите...
906 просмотров
schedule
31.03.2022
Я только что доказал, что сито Эратосфена менее эффективно, чем пробное деление?
Я пытался сравнить скорость выполнения двух алгоритмов: программы C грубой силы для печати простых чисел (10 000 чисел) и программы Sieve of Eratosthenes C (также 10 000 простых чисел).
Мое измеренное время выполнения алгоритма сита было: 0,744...
1254 просмотров
schedule
07.01.2023
Почему моя программа выдает мне все непростые числа, когда я прошу простые числа?
Я хочу использовать битовый массив и алгоритм сита Эратосфена, чтобы найти все простые числа в определенном диапазоне. Мой код компилируется, но он печатает все непростые числа, а не простые числа (кроме 2, потому что я прошу свою функцию Sieve...
286 просмотров
schedule
15.06.2022
Параллельное сито Эратосфена — Java Multithreading
Я хотел написать решето Эратосфена, которое будет работать с использованием определенного количества потоков. Я понял, что это будет работать следующим образом: Для 2 потоков до 17. Поток-1 берет 2 и начинает удалять кратные 2 из списка....
3498 просмотров
schedule
13.05.2022
