# 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.

667 questions
Filter by
Sorted by
Tagged with
17k views

### Load fifty million integers as quickly as possible in Java

I am working my way through Project Euler. Many of the problems deal with prime number calculations: this is the type of code that can be extracted into a separate class and reused. While calculating ...
6k 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 ...
7k views

### Calculation of prime numbers making use of Parallel.ForEach

In my spare time I decided to write a program that would systematically identify prime numbers from 2 to 18,446,744,073,709,551,615. This is for fun and learning, as I know it will take too long to ...
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 ...
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? ...
2k views

### Euler's Totient Function in x86 assembly (MASM)

My task was to implement Euler's totient function, and I'm looking for any and all criticism. ...
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 ...
5k views

### Checking if a number is prime in NASM Win64 Assembly

I'm just learning Assembly. This program is a simple attempt to determine if a given number is prime or not. Compiled as follows using VS2019 x64 Native Tools Command Prompt: ...
4k 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 ...
3k views

### First prime number larger than given integer

How can I test this C program for "efficiency"? The most interesting usage is that it returns negative output for large enough input, otherwise the behavior is about expected. Will you suggest how to ...
15k views

### Finding the 10001st prime

I'm solving Project Euler problem 7, which 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? Here's the ...
6k views

### Simple twin prime finder

I'm really new to coding so I'm looking for a bit of feedback on this twin prime finder. She works pretty decent but I know it could be better. ...
5k views

### Why is my Sieve of Eratosthenes using generators so slow

This is my prime sieve based on the Sieve of Eratosthenes. ...
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 ...
3k views

### Sieve of Eratosthenes in C

I have attempted to implement the Sieve of Eratosthenes in C. It works rather quickly with values tested up to ten million: time ./soe.out 10000000 returns ...
2k views

### Is this C++ naive primality test done right?

Here's my C++ code: ...
2k views

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 ...
5k views

### Python 3: Why is my prime sieve so slow?

I've implemented the sieve of Eratosthenes in Python 3 as follows: ...
2k views

### Eratosthenes sieve and MPI

I wrote this sieve of Eratosthenes with MPI, but I'm not sure if it's good enough. Should I use MPI_Scatter and MPI_Gather ...
3k views

### Generating prime numbers using Sieve of Eratosthenes with CUDA

I'm learning CUDA and wrote a little program which generates prime numbers using the Sieve of Eratosthenes. (I know the limitations of CUDA, specially with memory sizes and limits, but this program is ...
1k 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): ...
3k views

### Prime number generator exercise

I have been trying to create a class that would list prime numbers forever. I know it has already been done but I think I learned some valuable principles during my trials. This project helped me ...
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 ...
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 ...
663 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 ...
752 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...
24k views

### Generate nth prime number in Python

Today I had an interview, where I was asked to solve this problem: Generate nth prime number. Given a signature below, write python logic to generate the nth prime number: ...
4k views

### Nearly Illegible Prime Number Calculator

This is my first reasonably large C# program. Considering my code looks like it was written in an esolang to me, I'm guessing I did something wrong at some point. My main priority is readability, ...
1k views

### Prime Number Checker

This is my prime number checker in C++. I know that calculating the square root of a number can be very costly, so I don't do it unless the number is larger than 10k, where we would have to check ...
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. ...
2k views

### Wow that's a big integer! What's its largest prime factor?

I see that there are a few other people who have tackled Project Euler Problem #3. I hope you're not all sick of that question yet. I've not taken a look at those yet (purposely), but am about to now. ...
9k views

### Sieve of Eratosthenes in C++

I'm looking for some feedback on my implementation of the algorithm. How can I improve it? I ran into problems when calculating the larger prime numbers > 46349 due to integer overflow, but fixed that ...
2k 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 of test cases ...
5k views

### Tonelli-Shanks algorithm implementation of prime modular square root

I did an implementation of the Tonelli-Shanks algorithm as defined on Wikipedia. I put it here for review and sharing purpose. Legendre Symbol implementation: ...
6k views

### Rate my first python prime checker

I'm new to programming; I started about a week ago and started learning python. Currently, I only know some basic arithmetic operations in addition to some basic knowledge about lists, dictionaries, ...
2k views

### Prime sieve in Python

I was trying to write Sieve for the first time and I came up with this code: ...
2k views

### Find largest prime factor

Here is my attempt at solving Project Euler problem 3. It works for test numbers up to 9 digits long, but overflows when I input the real 12-digit behemoth. I've looked at other methods of solution, ...
2k views

### Prime generator in Python and C

I have written the Rabin-Miller test in Python and ported it to C. But somehow, the C version is ~20 times slower on my system, and I am not sure how. Anyway, here is my code. Python ...
2k views

### Express a number as sum of 2 primes

Problem: Given an even number (greater than 2), return two prime numbers whose sum will be equal to given number. NOTE 1: A solution will always exist. (Goldbach's conjecture) Note 2: If ...
871 views

### Project Euler “Largest prime factor” (#3) in Java

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I wrote the following code with help of some Java 8, I'll explain the equivalent to Java ...
3k views

### Project Euler #10 in C++ (sum of all primes below two million)

Project Euler Problem 10 asks for the sum of all the primes below two million. I'm creating a list of primes and keep checking any new number for divisibility with only prime numbers. I thought it ...
3k views

...
3k views

### Sum of First N Primes

Task: Print sum of first 1000 primes. ...
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 ...
4k views

### Python π = 1 + (1/2) + (1/3) + (1/4) - (1/5) + (1/6) + (1/7) + (1/8) + (1/9) - (1/10) …1748 Euler

I wrote this code to show that my reddit post is correct. After the first two terms, the signs are determined as follows: If the denominator is a prime of the form 4m − 1, the sign is positive; if ...
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 ...
3k views

### Unit Testing for isPrime function

I've decided that I want to take a stab at test first programming. So, before I tackled writing an isPrime function, I wrote this unit test. It's my first and I'm ...
1k views

### x64 Assembly - checking for largest prime factor

Using x64 assembly, I solved the Largest Prime Factor problem on Project Euler. The problem is as follows: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of ...
586 views

### Computing the n-th prime

I've written some Python 3 code that computes the $n$-th prime. I implemented first a naive isprime function that looks for divisors of $m$ between $2$ and $\lfloor \sqrt m \rfloor+1$. Then a ...
966 views

### Suggestions for improvement on Project Euler #7

Here is a solution for Project Euler Problem #7. 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 10,001st prime number? I've used ...