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
24
votes
4answers
7k views

Sieve of Eratosthenes - Python

I've been doing a lot of Project Euler lately and just wanted to make sure my implementation was as good as it could be. Does anyone have any suggestions to speed this up? ...
14
votes
7answers
4k views

Project Euler #3 - largest prime factor

I was going through the Project Euler problem #3 and made a program to solve it. The problem is as follows: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the ...
14
votes
3answers
636 views

Sieve31, my sieve of Eratosthenes returning IEnumerable<int>

This very fast, simple sieve quickly finds 31 bit primes. It uses a memory efficient BitArray for odd numbers. How a 32 bit int...
18
votes
1answer
1k views

Compile-time sieve of Eratosthenes

There are many instances of prime number sieve implementation both here and other places on the web, but I wanted something a little different. In particular, I wanted to create a static array of the ...
6
votes
0answers
400 views

Sieve32FastV2 - A fast parallel Sieve of Eratosthenes

I’ve created a much cleaner, better designed version to my parallel sieve. I’ve implemented most of EBrown’s micro-optimizations but also revamped the code on my own (that is not in direct response ...
7
votes
2answers
367 views

Prime generator for SPOJ

I have written code to solve the prime generator problem. I am given an input which contains in the first line the number of test cases, and for each test case, I am given a range and I have to print ...
3
votes
1answer
219 views

Sieve32, a simple 32 bit sieve returning IEnumerable<uint> using C#

What a difference 1 bit makes! This very fast, simple sieve of Eratosthenes quickly finds 32 bit primes. It uses a memory efficient BitArray for odd numbers – but ...
4
votes
1answer
2k views

Simplifying and optimizing factors and prime factorization generator

My first algorithm for finding the factors of a number was pretty slow and horrible (it started at \$O(n^2)\$, where n was not even the inputted number), but I eventually came up with this new code. ...
3
votes
4answers
2k views

Sieve of Eratosthenes: making it quicker

I was thinking about doing problem 23 of Project Euler. It includes the difficulty where you have to factorize primes. I had already done that in problems I solved earlier, but it was only necessary ...
33
votes
7answers
6k views

Project Euler #7 10001st prime

I decided to start working on the Euler project exercises. I'm doing fine for now but the seventh problem is running quite slow and I can't think of anything to make it work faster. It takes around ...
15
votes
4answers
3k views

Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and R

A friend of mine recently started learning R, and she complained to me that R is very slow. She was working on Project Euler Problem 7, which asks for the value of the 10001st prime number. For ...
14
votes
1answer
560 views

Large Number Limit Extravaganza

I am writing a program that computes $$n-n \cdot \left(\prod_{i=1}^n (1-\frac{1}{p_i})\right)$$ which is rewritten in my code as: $$\left(1-\left(\prod_{i=1}^n(1-\frac{1}{p_i})\right)\right) \cdot ...
14
votes
3answers
1k views

Prime Sieve and brute force

Got caught up with this morning's C++ question. So I thought I would have a go. SO here is my attempt at printing the first 1001 primes. ...
8
votes
5answers
5k views

Euler #3 largest prime factor

Problem Statement This problem is a programming version of Problem 3 from projecteuler.net The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of a given number N?...
8
votes
1answer
2k views

Prime Number Generator in Swift

I would like to make (or improve my function) a function that returns an array of integers containing all the prime numbers from 2...n that can execute as quickly ...
8
votes
6answers
4k views

Sum of all primes under 2 million

I have this assignment to write the optimized space and time code for finding the sum of all primes under 2 million. I'm using the following function to check if each number is prime: ...
15
votes
3answers
947 views

Wheel based unbounded sieve of Eratosthenes in Python

Answering this SO question recently, I've developed the following code (based on a well-known Active Code recipe, as discussed here): ...
12
votes
7answers
9k views

Sieve of Eratosthenes

For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation. I would like to hear some suggestions for improvements, especially how to make it more efficient ...
11
votes
2answers
144 views

Segmented wheel Sieve of Eratosthenes in Python

Here is a new version of a segmented and wheel factorized Sieve of Eratosthenes. It currently uses mod 30 wheel factorization to eliminate multiples of 2, 3, and 5 in the sieve data structure to gain ...
8
votes
2answers
197 views

Largest Prime Factor redux

There have been a number of questions asking for comments on code for the Project Euler problem to compute the largest prime factor of a number. A primary intent of this task is to find the factor as ...
8
votes
4answers
765 views

Prime generator

I'm coming from a Python background(look at indentation :) ) and trying to learn basics of C++. I wrote a simple prime generator, I know there is better algorithms, but I want advices about coding ...
7
votes
2answers
429 views

Postponed Prime Sieve in Swift

Motivated by this question, I looked out for other "infinite prime generators", i.e. functions which produce the list of prime numbers in increasing order and do not have an a-priori upper limit (such ...
5
votes
3answers
908 views

Prime number util class

A prime number util, which provides 3 APIs - find the nth prime, find the next prime, and find all primes up to n. I must admit this code has been influenced a lot by discussions here. I'm looking ...
5
votes
2answers
693 views

Prime Number calculation bottleneck

Inspired by another question here: Sum of Prime numbers under 2 million, I decided to try and implement Eratosthenes' Sieve from scratch using the algorithm described in the article. ...
5
votes
2answers
1k views

Prime Number Speed

I know prime number programs have been beaten to death. I have been programming for eight years (not that long, but I'm not in my 20s yet and I got a programming job straight out of high school so I'm ...
2
votes
2answers
565 views

Printing all the prime numbers between two bounds

I keep getting a time limit exceeded for this solution to SPOJ Prime1. I need to print all primes within a given interval (with intervals as large as 105, and numbers as large as 109). I've tried ...
2
votes
1answer
743 views

Unbounded Sieve of Eratosthenes in Swift

I've spent a while teaching myself Swift, and decided to take on the challenge of writing an unbounded Sieve of Eratosthenes to challenge myself. This is actually the first time I've written an ...
9
votes
1answer
1k views

Sieve32Fast - A very fast, memory efficient, multi-threaded Sieve of Eratosthenes

An improved version Sieve32FastV2 is available. The classical solutions for the Sieve of Eratosthenes fall into 2 camps: one uses a bool[], which is fast but very ...
8
votes
2answers
959 views

Sieve of Eratosthenes implementation is running slowly

I have written this code to find prime numbers, and it works well, but the calculation speeds are incredibly slow. Am I doing this wrong? I know that I might be really doing this the wrong way, but ...
8
votes
1answer
140 views

Segmented and wheel factorized prime generator in Python

I recently discovered that it is much faster to generate primes using a Sieve of Eratosthenes (SoE) with a boolean array data structure than with a heap. Since then I have been looking for fast and ...
6
votes
1answer
490 views

Project Euler #10 in Swift - Summation of primes

I just finished Project Euler #10 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. I hope I learned some from ...
6
votes
4answers
1k views

Threshing: Sieve of Eratosthenes

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly. I made this super simple, trying to learn a little bit about ...
5
votes
3answers
856 views

Project Euler Problem #10

I've read other solutions about solving the 10th problem for Project Euler (finding the sum of all prime numbers under 2,000,000) but I wanted to try it on my own using the Sieve of Eratosthenes ...
40
votes
5answers
5k views

Parallel sieve of Eratosthenes

For the first time, I tried to use threads by myself in order to implement a parallel sieve of Eratosthenes. The trick is that each time a prime is found, a thread is spawned to eliminate all the ...
14
votes
4answers
1k views

Codechef: Prime Number Generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers! Input The input begins with the number t ...
9
votes
4answers
2k views

A faster way to compute the largest prime factor

I am self-learning js and came across this problem(#3) from the Euler Project The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? ...
8
votes
4answers
10k views

Fast Number Factorization in Python

Here's my implementation to factorize a positive integer: ...
7
votes
7answers
4k views

Sum of the digits is prime or not

Puzzle Description: A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? How can I ...
5
votes
3answers
3k views

Calculate highest prime factor very slow

Sometimes when I write a Python 3.x script with too many nested loops and some big values it just takes too long to give the answer. How can I optimize my code so that it runs faster, or where should ...
23
votes
4answers
3k views

Prime number generator in C++

I am slowly learning C and C++, and decided after a few lessons to dive in myself without any help. I developed this prime number generator. It seems fast, but I'm wondering if I'm following the best ...
11
votes
5answers
3k views

Prime Number Sieving Algorithm

Last semester in my Masters Program I developed this code for sieving. My professor wants me to write a report that he might use locally within the school, but I feel like I've done nothing that new, ...
10
votes
3answers
3k views

Find the Nth number divisible by only 2,3,5, or 7

I recently participated in a small friendly competition and this was one of the questions: A number whose only prime factors are 2, 3, 5 or 7 is called a humble number. The first 20 humble ...
8
votes
2answers
991 views

Remake of factoring/prime factorization calculator

Background info on factoring and prime factorization. I've remade this program from my first attempt, and I'm sure it can still be improved. My questions: These calculations should only be done ...
6
votes
2answers
11k views

What is the 10001st prime number?

Project Euler problem 7 says: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number? I believe that my code is ...
5
votes
3answers
26k views

Prime factorization of a number

I'm trying to learn Python through the excellent online book Dive Into Python 3. I have just finished chapter 2 about data types and felt like trying to write a program on my own. The program takes ...
5
votes
4answers
2k views

Any better way to solve Project Euler Problem #5?

Here's my attempt at Project Euler Problem #5, which is looking quite clumsy when seen the first time. Is there any better way to solve this? Or any built-in library that already does some part of the ...
4
votes
3answers
1k views

Project Euler #5 (LCM of [1, 2, …, 20])

I have implemented a solution to Project Euler problem 5: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive ...
25
votes
5answers
1k views

Count distinct primes, discarding palindromes, in under 2 seconds

Problem Statement Generate as many distinct primes P such that reverse (P) is also prime and is not equal to P. Output: Print per line one integer( ≤ 1015 ). Don't print more than 106 ...
18
votes
2answers
2k views

Thread-safe prime number source

I am working on some multi-threaded code that requires a prime-number source. The following code keeps an array of primes in memory, extending it as needed. It works in the 'int' domain, being ...
12
votes
3answers
2k views

Finding largest prime factor from inputted number

This is my first C# console application. This program asks for an input of a number, and finds the highest prime factor of that number. Please review my code. Have I used things right? Is my code ...