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
11
votes
3answers
2k views

Prime sieve in Python

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

Sum of First N Primes

Task: Print sum of first 1000 primes. ...
11
votes
6answers
1k views

Find primes using “naive” algorithm

I know I can use Sieves to make this faster, but I wondered if there's anything I'm missing with this implementation of the "naive" algorithm. On my PC running the command (first million primes): ...
11
votes
2answers
4k views

Find prime factors in C++

Please review this code. ...
11
votes
4answers
397 views

Threshed and Malachi'd: Sieve of Eratosthenes

I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes. This may be bordering on code-golfing, but I think that I have a pretty good piece of code here. Is ...
11
votes
4answers
1k views

Calculating primes until a user-given value

I am new to C# programming. I wrote a little program in C# to calculate all primes until a user-given value. Ignoring the lack of computing power I wrote this program to handle theoretically very huge ...
11
votes
4answers
2k views

Project Euler Problem 35: counting circular primes below 1 million

Project Euler Problem 35 asks: The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. How many circular primes are there ...
11
votes
4answers
415 views

Factorizing integers

I'm working on this method in Java, which is giving me the factors of a number. I'll be using this method a lot, and I was wondering if there isn't a better way of doing it. Like, with just one loop. ...
11
votes
3answers
1k views

Parallel sieve of Eratosthenes, version 2

This question is a revision of Parallel sieve of Eratosthenes. The goal is to implement a sieve of Eratosthenes with parallel strikes out from the boolean array. I tried to fix the data races and all ...
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, ...
11
votes
2answers
724 views

Breadth First Search to find connected primes

I've been working through the British Informatic Olympiad's 2016 Paper, and I've been struggling with some of the larger cases for question 3, specifically the larger cases on the mark scheme (the 3 ...
11
votes
3answers
572 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 ...
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 ...
10
votes
9answers
5k views

Find the nth prime between 1 and 1,000,000 in under 3 minutes - follow-up

Previous question: Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes My mission is to find the nth prime number, based on user input 1-1,000,000. ...
10
votes
5answers
981 views

Largest Prime Factor (PE3) using OOP

I want to learn some C# syntax/paradigms (I'm more used to Java), and have been wanting to get a bit better at math as well, so I solved ProjectEuler3: Largest prime factor with the following small ...
10
votes
4answers
3k views

Prime Factorization

I'm doing an Objective-C project and I need to do some prime factorization and so I came up with the following algorithm which is 99% C, except for the array part which was easiest to implement in ...
10
votes
6answers
3k views

Determine if number is a prime number

I made a function that takes an argument x and returns True if x is a prime number and ...
10
votes
4answers
2k views

Is_prime check in Python: can this be more pythonic?

I have the following function that checks if a number is prime: ...
10
votes
4answers
2k views

Find the sum of prime numbers below 2 million

This code is trying to find the sum of prime numbers below 2 million. The code does work as intended, but it takes a very long time ( 6 minutes) for the code to execute completely. What is the problem ...
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 ...
10
votes
3answers
393 views

PrimeFactorize method for int

I have written this PrimeFactorize utility method in C# (using LINQPad) which works fine, but feels like it is a bit slow, I was wondering what might be improved. ...
10
votes
7answers
3k views

Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes

My mission is as the title states. Here is the original code, before optimizing slightly (but still not enough). Revised code is in my answer, and it still needs work. Also, I want to write this ...
10
votes
4answers
1k views

Sieve of Eratosthenes optimization

I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code? ...
10
votes
5answers
1k views

Sieve of Eratosthenes in C++11

Please point out every problem you see with this code. Any fundamental flaws, naming conventions, design decisions, you name it. ...
10
votes
3answers
370 views

SSE loop to walk likely primes

This is a continuation of a discussion that was started here. While there are some interesting points there about instruction timing and latency, it is not necessary to read that Question to ...
10
votes
3answers
210 views

Project Euler Problem 10. Sum of all primes < 2mil

I'm new to coding so I can't create complex code yet. I do as much as I can with fors and ifs, since while I know a bit about ...
10
votes
2answers
438 views

Number factorization in clojure

I'm just a Clojure noob (started learning yesterday). Here is my helloworld program. It factorizes number into primes. Do you have any comments? How could I make this code cleaner and shorter? Maybe I ...
10
votes
2answers
671 views

Swift replacement for C's for-loop

I recently wrote an entry on my blog regarding unit testing using prime numbers as an example. When I wrote the entry, I wrote my code keeping in minding that proposal SE-0007 has been accepted for ...
10
votes
1answer
85 views

Complete factorization in ><>

Maybe a somewhat odd choice of language, but here is a program in ><> I have tried to optimize the execution time of. (Not golfing). The efficiency is measured in the number of required ...
9
votes
3answers
4k views

Printing all primes < 1,000,000 to a text file

It takes a long time to execute and the CPU usage for the executable is about 25% while it is executing. Any ideas on how to make this faster? primes.c: ...
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 ? ...
9
votes
2answers
12k views

Finding prime factors of a number?

Okay, so just having a little fun I thought I'd see if I could write an algorithm to find all of the prime factors of a number. The solution I came up with is as follows: ...
9
votes
3answers
3k views

Sieve of Eratosthenes in Java

Here you can find my implementation of sieve of Eratosthenes in Java. ...
9
votes
2answers
722 views

Prime factorization of a natural number greater than 1

I want to write a program in Java that return a prime factorization of any natural number greater than one. After spending some time coding and debugging, the program runs fine. Since I am new to ...
9
votes
3answers
2k views

Greatest prime number smaller than N where N can be as large as 10^18

This is code for finding largest prime number smaller than \$N\$, where \$N\$ can be as large as \$10^{18}\$. But, it takes 1 minute for \$10^{18}\$. I need to pass it in 2-3 sec. What changes ...
9
votes
4answers
5k views

Project Euler Problem #7 in Python (10001st prime number)

I have managed to solve the 7th Project Euler problem, however I think it can be improved by a lot, I am by no means a professional programmer or even consider myself really good at it. Any ...
9
votes
2answers
533 views

Finding prime divisors with wheel factorization

I am just starting to learn C++, and I wrote was the following implementation of the trial division algorithm to find the prime factors of a positive integer. I'm hoping the community here can suggest ...
9
votes
3answers
600 views

A reference source for primes up to 64K (for unit tests)

In order to code the tests for my number theory library (a collection of routines that proved handy for coding challenges) I needed a reference source for primes up to 2^16. I did not want to ...
9
votes
1answer
552 views

Prime factorization in F#

In the pursuit of learning F#, I have been working through some Project Euler problems. This is my solution for problem 3: ...
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
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
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
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: ...
8
votes
4answers
5k views

Finding Primes in Java

I have a prime-finding class here that needs improvement. Sample result: ...
8
votes
4answers
5k views

Printing 100 prime numbers

This is a program I wrote to print out 100 prime numbers. How can I improve it? ...
8
votes
1answer
488 views

Prime sieve for all primes up to a number

As a beginner to C++, I wanted to make something using what I was learning, so I did this to learn about arrays. This implements the Sieve of Eratosthenes to find the primes up to a limit. I didn't ...
8
votes
6answers
8k views

Program for finding Fibonacci primes

I think it could have been designed with more object orientation. I don't like how one of my methods calls another from within the method, but I wasn't sure how to return the result because it is a ...
8
votes
2answers
834 views

Primes and SemiPrimes in Binary

I'm in the midst of re-learning python. My current effort is an implementation around prime factorization. I am attempting to reproduce something similar to the table found here (in binary): https://...
8
votes
4answers
12k views

Yet another prime number generator

The question asked to find all the prime numbers within a particular range. The way I approached this was to loop through each of the numbers within the range and for each number check whether it's a ...
8
votes
1answer
3k views

Project Euler 407: Is there any more optimal way to solve this idempotent equation (modulo n ring)?

Project Euler problem 407: If we calculate a2 mod 6 for 0 ≤ a ≤ 5 we get: 0, 1, 4, 3, 4, 1. The largest value of a such that a2 mod 6 = a is 4. Let's call M(n) the largest value of a < n ...