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.

Filter by
Sorted by
Tagged with
12
votes
1answer
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: ...
12
votes
2answers
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 ...
12
votes
2answers
2k views

Quadratic sieve

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 ...
12
votes
1answer
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: ...
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
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 ...
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
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. ...
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
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 ...
11
votes
2answers
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 ...
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
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 ...
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
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. ...
10
votes
7answers
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 ...
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
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 ...
10
votes
3answers
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 ...
10
votes
2answers
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 ...
10
votes
2answers
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 ...
10
votes
1answer
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 ...
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
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: ...
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
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://...
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
4answers
14k views

Fast Number Factorization in Python

Here's my implementation to factorize a positive integer: ...
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
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 ...
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
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 ...
9
votes
2answers
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 ...
9
votes
2answers
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 ...
9
votes
2answers
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 ...
9
votes
3answers
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 ...
9
votes
1answer
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: ...
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
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 ...
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? ...

1
2
3 4 5
14