What's the deal with Deno? We talk with a major contributor to find out. Listen now.

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

658 questions
Filter by
Sorted by
Tagged with
324 views

### Depth-first search method for searching for all “superpalindromes” whose prime factors are all <=N

A question was asked over at math.SE (here) about whether or not there are infinitely many superpalindromes. I'm going to rephrase the definition to a more suitable one for coding purposes: ...
4k views

### First attempt at generating prime numbers

I had to look up some other solutions online because I could not figure it out on my own. I really wish I could have come up with it completely on my own, but that didn't happen. Nevertheless, please ...
2k views

Here is an implementation I pieced together from various papers on the subject. It took a lot of fiddling to get it to run at all. My ideas for better performance and readability, based on looking ...
1k views

### Sieve of Atkins algorithm

I got the inspiration to write this algorithm from this question. The OP cited the Sieve of Atkin as one of the fastest ways to generate primes. So I figured I would give it a try: ...
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): ...
4k views

### Find prime factors in C++

Please review this code. ...
399 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 ...
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 ...
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 ...
419 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. ...
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 ...
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, ...
730 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 ...
304 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 ...
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. ...
988 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 ...
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 ...
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 ...
2k views

### Is_prime check in Python: can this be more pythonic?

I have the following function that checks if a number is prime: ...
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 ...
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 ...
396 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. ...
4k 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 ...
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? ...
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. ...
413 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 ...
215 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 ...
504 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 ...
706 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 ...
86 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 ...
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: ...
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: ...
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 ? ...
845 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://...
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: ...
14k views

### Fast Number Factorization in Python

Here's my implementation to factorize a positive integer: ...
3k views

### Sieve of Eratosthenes in Java

Here you can find my implementation of sieve of Eratosthenes in Java. ...
737 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 ...
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 ...
7k 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 ...
118 views

### Factorize All Numbers Up to a Given Number

this post is sort of a continuation of my answer on the following question: Fast Algorithm to Factorize All Numbers Up to a Given Number. As this post explains - We need to factorize all the numbers ...
569 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 ...
201 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 ...
604 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 ...
613 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: ...
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 ...
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?...
971 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 ...