Публикации по теме 'sieve-of-eratosthenes'
Сито Эратосфена
Добро пожаловать в первую публикацию категории «Давайте решим»!
Сегодня я объясню вам, что такое Решето Эратосфена на самом деле. Это простой и полезный алгоритм для программистов. Особенно для тех, кто интересуется соревновательным программированием.
Если вы еще этого не сделали, обязательно ознакомьтесь с серией LitCodes Competitive Programming. Реализация кода в сегодняшней публикации выполнена на C++.
Проверить:
Что такое соревновательное программирование?..
Количество простых чисел
Вопрос. Подсчитайте количество простых чисел, меньших неотрицательного числа, n .
Пример:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
Полностью вопрос можно посмотреть здесь .
Подход 1. Начнем с самого очевидного —
//Approach 1:
//Runtime: 465ms
//Memory usage: 32.8MB
class Solution {
public int countPrimes(int n) {
int count = 0;
for(int i = 2; i<n; i++){
if(isPrime(i)){..
Сито Эратосфена
Я наткнулся на электронное письмо, в котором упоминалось алгоритмическое сито Эратосфена. Это алгоритм нахождения всех простых чисел до предела. Вы можете прочитать больше об этом здесь".
Письмо пришло с псевдокодом, но я решил прочитать о нем больше и написать для него код. Я нашел видео на YouTube, которое очень хорошо объяснило это, и я был готов к работе. Видео ниже.
Код, который я придумал, приведен ниже.
Есть блог, на который я подписался, чтобы публиковать..
Вопросы по теме 'sieve-of-eratosthenes'
Сито Эратосфена в рубине
Вместо того, чтобы копировать Ruby-версию этого алгоритма из сети, я хотел создать свою собственную на основе его описания здесь . Однако я не могу понять две вещи
def primeSieve(n)
primes = Array.new
for i in 0..n-2
primes[i] = i+2...
7817 просмотров
schedule
08.11.2022
Программа для поиска простых чисел
Я хочу найти простое число от 0 до длинной переменной, но не могу получить никаких результатов.
Программа
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program...
130624 просмотров
schedule
08.04.2022
нахождение всех простых чисел в заданном диапазоне
Я пишу эту Java-программу, которая находит все простые числа в заданном диапазоне. Поскольку я имею дело с действительно большими числами, мой код кажется недостаточно быстрым и дает мне ошибку времени. Вот мой код, кто-нибудь знает, как сделать его...
7846 просмотров
schedule
06.05.2023
Почему этот простой тест такой медленный?
Этот код был взят из книги "Haskell Road to Logic, Math and Programming". Он реализует алгоритм решета эратосфена и решает проблему 10 проекта Эйлера.
sieve :: [Integer] -> [Integer]
sieve (0 : xs) = sieve xs
sieve (n : xs) = n : sieve (mark...
825 просмотров
schedule
14.10.2022
Список простых чисел с использованием метода Sieve с использованием битовой маски
Я написал следующий код, чтобы перечислить все простые числа до 2 миллиардов, используя метод Sieve. Я использовал битмаскирование для целей маркировки. Хотя я могу правильно получить простые числа, несколько простых чисел в начале каждый раз...
859 просмотров
schedule
14.08.2022
Многопоточное сито Эратосфена — очень-очень долго
Я пытаюсь создать многопоточное сито Эратосфена.
Количество потоков по умолчанию установлено равным 4, хотя они могут быть указаны пользователем в качестве аргумента командной строки.
Я пытаюсь отметить все интервалы простого числа в массиве...
2377 просмотров
schedule
07.05.2022
Алгоритм решета Эратосфена в C
Итак, эта функция, которую я создал, использует алгоритм Решета Эратосфена для вычисления всех простых чисел ‹= n. Эта функция хранит в параметрах простые числа и количество простых чисел.
Когда функция завершается, простые числа должны указывать...
4005 просмотров
schedule
10.06.2022
Является ли это оптимальным простым генератором?
Является ли это каким-либо образом оптимальным решением для нахождения простых чисел? Я не пытаюсь добавить каждую оптимизацию на свете, но хороша ли основная?
def primesUpto(self, x):
primes = [2]
sieve = [2]
i = 3
while i <=...
424 просмотров
schedule
04.02.2023
Понимание сита Эратосфена в Python
Я нашел пример кода на Python, который выдает все простые числа до n , но я его просто не понимаю. Почему он делает то, что делает?
Я прочитал статью в Википедии о Сите Эратосфена , но просто не знаю, как это работает .
pp = 2
ps = [pp]
lim...
1878 просмотров
schedule
17.03.2023
Количество различных простых делителей числа
Q: Даны A, B и K. Найдите все числа от A до B (включительно), которые имеют K DISTINCT простых множителей. Вот что я сделал. Я реализовал решето Эратосфена и вычислил все простые числа до верхней границы A, B. Затем я перехожу к поиску того, какое...
4705 просмотров
schedule
27.06.2023
Не печатается желаемый результат для сита эратостена
Я пытаюсь создать программу, которая выводит список простых чисел с заданным входным значением n.
Функция SieveEratosthenes, которую я сделал: - генерирует список простых чисел по первым n целым числам - создает хранилище для списка сгенерированных...
62 просмотров
schedule
04.12.2022
Решето Эратосфена Удаление элементов списка
Я работал над книгой Страуструпа: https://rads.stackoverflow.com/amzn/click/com/0321543726 В настоящее время я работаю над упражнением 13 главы 4, в котором вам предлагается реализовать алгоритм решета Эратосфена для нахождения простых чисел между...
251 просмотров
schedule
01.12.2022
Почему я получаю ошибку bad_alloc при реализации Решета Эратосфена
Я пытаюсь предварительно вычислить все простые числа. в большом диапазоне от 1 до 1000000005, используя Sieve of Eratosthenes, но получая ошибку после компиляции моего кода... Я думаю, что проблема связана с размером вектора, но когда я распечатал с...
60 просмотров
schedule
30.11.2022
Как вспомнить функцию, Решето Эратосфена
Я пытаюсь написать код, который будет вычислять простые числа с помощью решета Эратосфена. Я должен включить функцию, которая будет принимать число и пересекать все числа, кратные этому числу. Для тестирования я установил первое число равным 2, а...
101 просмотров
schedule
07.11.2022
Код Haskell для исключения чисел для решета Эратосфена не работает должным образом
Я пришел со следующей реализацией Sieve of Eratosthenes :
sieve :: (Integral a) => [a] -> [a]
sieve [] = []
sieve (p:ps) = p:[x | x <- sieve ps, (rem x p) /= 0]
primes :: (Integral a) => [a]
primes = sieve [2..100]
Вызов...
98 просмотров
schedule
08.02.2023
Путаница с набором и реализацией решета Эратосфена
Я хотел сначала предисловие, что я новичок в python и что я любезен со всеми, кто может объяснить это мне ясно и полностью.
Я смотрел на код, найденный в ссылке ниже:
http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python
Я только начал...
74 просмотров
schedule
09.03.2024
Алгоритм - Что не так с этим решением решета Эрастотена
Я думал, что создам свою собственную реализацию алгоритма решета, чтобы быстрее находить простые числа. Удивительно, но это не проходит ряд тестов.
Вот мой алгоритм в Ruby для определения, является ли число простым.
def prime?(n)
primes =...
126 просмотров
schedule
13.04.2022
Как перебирать матричные элементы Matlab
У меня есть задача создать фрагмент кода Matlab, который использует сито Эратосфена для поиска списка простых чисел до N. Я создал цикл, который находит не простые числа, а затем находит значение индекса их в списке от 2 до N. Как мне заставить мою...
485 просмотров
schedule
01.11.2022
Решето времени исполнения Эратосфена в haskell
Я новичок в Haskell и писал код для решения проблемы решета Эратосфена с использованием списков. Вот код
primes m = 2 : primes' m [3,5 ..m] [] where
primes' m integers@(p : xs) acc | p*p>m = reverse acc ++ integers...
105 просмотров
schedule
06.06.2022
Решето Эратосфена — реализация на языке C
Я что-то упускаю, но не могу найти что. Мне также дали файл input2.c, и в нем есть функция print_prim, которую мне не разрешено изменять.
Для n=10 всегда печатается
4, 5, 7, 9,
Я знаю, что в функции print_prim есть i+2, но я не могу...
259 просмотров
schedule
05.01.2023
