Skip to main content

Questions tagged [primes]

Primes or prime numbers are numbers which are divisible only by themselves and one, starting with 2, 3, 5, 7, 11.... They are commonly used in encryption and hashing algorithms.

Filter by
Sorted by
Tagged with
5 votes
0 answers
70 views

Optimizing SymPy Implementation of prime factorization in form of QUBO

I'm trying to reproduce a paper on Prime Factorization. This paper converts the problem into a QUBO form, which then we can map it to an Ising Minimizer. I've basically done everything and I've ...
Amirhossein Rezaei's user avatar
2 votes
1 answer
129 views

Count how many numbers in a range have exactly three divisors

The challenge Given array a of n numbers, I need to count how many positive numbers less than each aᵢ have exactly 3 divisors. Constraints 1 <= aᵢ <= 2.5 * 10¹³ In other words, the minimum ...
Muhammad Usman's user avatar
6 votes
4 answers
435 views

Optimal Solution for the Four Divisors Problem on LeetCode

I recently encountered the Four Divisors problem on LeetCode and managed to achieve a 100% beat rate with my solution. I'd like to share it with you all and gather feedback on its effectiveness and ...
BrunoBarreto's user avatar
3 votes
1 answer
131 views

Miller-Rabin implementation is very slow

I implemented the Miller-Rabin-Primetest in python3. But I have the feeling it is very slow. I know that there are faster version in gmpy2 package, but I want to compare it with another code I have in ...
Lereu's user avatar
  • 141
1 vote
2 answers
119 views

Miller-Rabin prime test

I have an implementation of the Miller-Rabin prime test, coded in Python 3. I want to use that as a comparison to a prime test which I coded myself. Unfortunately I have no idea how "fast" ...
Lereu's user avatar
  • 141
9 votes
1 answer
291 views

Construct a performant sieve of Atkin in Rust

I have implemented the sieve of Atkin in Rust. It can find all primes till 1,000,000,000 in 4.5 s using 34.4 MiB on my 1.4 GHz machine. This is a direct implementation (with some optimisations made ...
tfpf's user avatar
  • 193
6 votes
2 answers
961 views

C code for finding prime numbers

I have created a program to find prime numbers up to the 32nd power of 2. It uses the sieve of Eratosthenes. I would appreciate it if you could let me know any bugs or improvements I can make. ...
Haruo Wakakusa's user avatar
1 vote
1 answer
100 views

Project Euler 10(Python) | Summation of Primes

This is my Python3 code which solved the 10th problem of Project Euler. I haven't passed the last 2 time limit test cases. ...
peternish's user avatar
3 votes
1 answer
271 views

Project Euler 60: Prime Pair Sets

Project Euler Prime Pair Sets: The primes 3, 7, 109, and 673 are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 ...
peternish's user avatar
3 votes
1 answer
69 views

Find perfect and amicable numbers

I've been playing with perfect, amicable and social numbers lately, and created a class for investigating these. At present, it has functions to return the perfect and amicable numbers in a specified ...
Toby Speight's user avatar
  • 76.9k
4 votes
2 answers
1k views

Miller-Rabin Primality Test in Python

I have the following implementation of the Miller-Rabin test in Python: ...
pointySphere's user avatar
4 votes
2 answers
719 views

Performance of Haskell prime sieve

I have this code, which is a pseudo-Sieve of Eratosthenes for generating primes: ...
Ari Fordsham's user avatar
3 votes
1 answer
146 views

Hunting for the 100,001st prime in Rust

Most of my programming experience is in Python, but my first language was C, and I was intrigued by the combination which Rust offers: a streamlined syntax and no manual memory management, but with ...
Tom Hosker's user avatar
2 votes
2 answers
133 views

generate prime factors via wheel factorization

I want to factor random values of n that range from uint.MinValue to uint.MaxValue as ...
Kittoes0124's user avatar
  • 1,940
3 votes
1 answer
126 views

Prime sieve in Rust

Using Sieve of Eratosthenes, I created a function that returns a vector of primes up to given limit. ...
manungsa's user avatar
17 votes
4 answers
2k views

Make an image where pixels are colored if they are prime

This code creates a black-and-white image of variable size where the n-th pixel is white if n is a prime number and black if it isn't. It works, but I wonder if it is well written or if it could be ...
Dornteufel's user avatar
3 votes
1 answer
207 views

Find factor pairs of an integer in Rust

I'm trying to efficiently generate all pairs of factors of a number n. For example, when n=27, the factor pairs are (1, 27), (3, 9), (9, 3), (27, 1) The order in which the pairs are found is not ...
Bram's user avatar
  • 93
1 vote
0 answers
80 views

Strong Goldbach Conjecture with set implementation

I have devised my own version for a Goldbach verification project which uses sets to compare already sieved primes. My implementation also uses generators to "sieve a segment" since storing ...
Kevin Perez's user avatar
4 votes
1 answer
548 views

Prime factorization algorithm by using the multiprocessing module of Python

I may introduce a Python code of prime factorization which is from my personal project that I'm working on. ...
MYUN's user avatar
  • 59
1 vote
1 answer
133 views

Numpy segmented Sieve Of Eratosthenes

For the segmented Sieve Of Eratosthenes, I have devised the following code provided. And I understand that it is not the best implementation; However, it should be much quicker than what it is now. ...
Kevin Perez's user avatar
3 votes
1 answer
252 views

Find primes using Wilson's Theorem

The following code is an instantiation of wilson's theorem. It uses a simple factorial and division theorem to check for primality. My issue is with the performance of the code, and there are two most ...
Kevin Perez's user avatar
5 votes
1 answer
82 views

Möbius function using iterators for prime factors

While working on Project Euler, I have come across a few questions involving usage of the little omega function, big omega function, and Möbius function. My prior code wrote factors into an array and ...
Ethan Slota's user avatar
2 votes
1 answer
122 views

Multithreaded segmented Sieve of Eratosthenes

I am fairly new to Rust and thought a good way to practice would be to write a multithreaded segmented Sieve of Eratosthenes. It performs ok (searches ten-billion numbers in about 11 seconds on my ...
knots427's user avatar
1 vote
1 answer
172 views

Euler's totient function for large numbers

I made this algorithm to compute Euler's totient function for large numbers. A sieve is used. ...
user140242's user avatar
1 vote
0 answers
189 views

Benchmarking an improved wheel sieve

I followed your answers for my last questions (1st 2nd) and I came up with these new versions of my codes but I face some difficulties to measure the efficiency of my code, I use chrono library to ...
Ahmed Diab's user avatar
2 votes
1 answer
310 views

Prime sieve for large numbers

I state that I am not an expert and that certainly the code can be improved. I made this prime number sieve to be able to handle large numbers. The basic idea is to write a number p=r+bW*k where r is ...
user140242's user avatar
0 votes
1 answer
198 views

Find factors of a Mersenne number

On RosettaCode I found this C++ version of modPow (compute 2ᵖ mod n) to find the factors of a Mersenne number. ...
user140242's user avatar
0 votes
2 answers
701 views

Next level Improved Sieve of Eratosthenes

This is the next development for the Sieve of Eratosthenes algorithm, where all the multiples of 2,3 and 5 are eliminated, which will not take any memory or time. As my last question Improved Sieve of ...
Ahmed Diab's user avatar
8 votes
7 answers
4k views

Improved Sieve of Eratosthenes

How can I get to a perfect coding for this algorithm? I made the mathematical theorem, which is a development of the Sieve of Eratosthenes algorithm. I might use some help in coding. You can find the ...
Ahmed Diab's user avatar
4 votes
2 answers
200 views

Project Euler #51: "Prime digit replacements" in Rust

Problem: https://projecteuler.net/problem=51 "Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime ...
sarema's user avatar
  • 449
3 votes
1 answer
116 views

Fast way to compute a^d mod n

For a Miller-Rabin primality test I need a fast way to compute a^d mod n. Where a is one of 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Goswin von Brederlow's user avatar
4 votes
2 answers
1k views

Calculate the first largest factor of 600851475143

ٍProblem description: The prime factors of 13195 are 5, 7, 13 and 29. Largest prime factor 13195 is 29. What is the largest prime factor of the number 600851475143 ? Prime Factor: any of the prime ...
Amir Motefaker's user avatar
1 vote
0 answers
119 views

Count SemiPrimes task from Codility

I'm trying to solve the following exercise from codility: A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13. A ...
Karol Borkowski's user avatar
1 vote
2 answers
229 views

Clojure Prime Numbers from 1 to 1000

I am a beginner to Clojure and I made a little script that prints out every prime number from 1 to 1000. Let me know if there are any improvements that I can make: ...
code writer 3000's user avatar
3 votes
1 answer
155 views

A simple JavaScript function that does prime factorization

This is a simple JavaScript function that does prime factorization. I wrote it on an Android phone with online editor (I don't have access to computers in night time): Code: ...
Ξένη Γήινος's user avatar
2 votes
3 answers
411 views

Find prime numbers

I wanted to create a program that lists all prime numbers to a given upper bound and that will also provide the amount of primes in the set. After many hours of trial and error I was able to solve it. ...
Lax's user avatar
  • 21
3 votes
0 answers
257 views

Prime number generator in lisp

My implementation is based on the incremental prime sieve described on Wikipedia. I'm relatively new to lisp so I would appreciate any comments on my coding style or on the algorithm. The below code ...
rose's user avatar
  • 325
1 vote
1 answer
58 views

C code for discovering numbers with interesting/beautiful/symmetric properties

Below is a C code that generates 1000 random positive integers, for each number we check primality, palindromic property, and the square root of the sum of the digits. The purpose is to find/discover ...
Redsbefall's user avatar
  • 1,132
3 votes
2 answers
155 views

Factor 999999 numbers as fast as possible

My code finds the prime factorization of numbers, ordering the prime numbers from least to greatest. It prints a list of 999999 prime factorizations (which can be changed if you edit the function call ...
Some Guy's user avatar
  • 131
2 votes
1 answer
168 views

Sieve of Eratosthenes in F#

after looking at the pseudocode for the Sieve of Eratosthenes on wikipedia I tried implementing a similar version using F#. The code runs just fine, that is, it returns all prime numbers up until a ...
Antônio Salomão's user avatar
3 votes
2 answers
410 views

Prime numbers iterator

I am not familiar with iterators. I am confused with the traits approach and the traditional one. I don't know which one I should use in 2021. I wrote a minimal ...
nowox's user avatar
  • 1,099
3 votes
1 answer
921 views

Average prime number from array- Javascript

My mission is to solve this: Write a function that will take an array of numbers, and will return the average of all numbers in the array that are prime number. So far I wrote this: ...
Dar_ky's user avatar
  • 83
3 votes
2 answers
210 views

Generating prime numbers quickly in rust

I am attempting to re-implement a postponed sieve algorithm for generating prime numbers in Rust. I am able to make a solution that works, but I have to use a couple of ...
kbrose's user avatar
  • 151
1 vote
2 answers
151 views

Improving Project Euler code problem #10

So, I just finished Problem 10 on Project Euler, but it took about 3 to 4 minutes for my output to come out, due to bad coding, I guess, any suggestions on how could I optimize my code? Question The ...
fabinfabinfabin's user avatar
4 votes
4 answers
215 views

My prime number generation program in Python

So I did my own take (I wrote my own algorithm) for generating prime numbers from 1 to 1000. ...
Aryan's user avatar
  • 51
0 votes
2 answers
213 views

My prime sieve using Python

...
Aryan's user avatar
  • 51
0 votes
2 answers
206 views

A function to find all the primes between two numbers whose reverse is also a prime and doesn't include palindrome, in JS

I am trying to solve a challenge in which I have to write a function that takes in two numbers as arguments and returns an array containing numbers between them which are prime and their reverse is ...
Valoruz's user avatar
  • 103
13 votes
1 answer
336 views

Sieve of Eratosthenes in Vyxal

I'm trying to learn the golfing language Vyxal because I occasionally contribute to it, and I'm slightly ashamed I can't even use it. To do this, I started with implementing the Sieve of Eratosthenes ...
user's user avatar
  • 529
3 votes
2 answers
527 views

Python – return list (or not?) of prime numbers between two numbers

I'm trying to learn how to write code well in Python. I've been tinkering with a function that will return a list of all prime numbers between the two parameters. This is the best I could come up with ...
Ramen Enthusiast's user avatar
1 vote
3 answers
210 views

Count prime numbers whose rotations are all prime

This code solves Project Euler problem 35: The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. There are thirteen such primes ...
SSSNIPD's user avatar
  • 39

1
2 3 4 5
15