# 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
228 views

### Fermat Factorization

Please review my implementation of Fermat's Factorization. ...
264 views

### Sieve of Eratosthenes and twin prime finder

I made this program to find primes and twin pairs. I'd like feedback on anything from formatting to content to technique. In short: how would this be different if it was written by an experienced ...
141 views

### Sum of primes in given range in Go

This piece of code calculates the sum of all prime numbers below 1 million. It stood out to me that the Ruby script is around 20% faster. I know that Go should be faster just for being a compiled ...
138 views

### Strange performance difference

For exercise, I wrote this code: ...
473 views

### Prime Numbers Store

Let's say we need to create a store for selling prime numbers. Users enter the store and ask to buy a number. If the number asked is a prime number, 1.1. then it's either available for sale 1.2. ...
331 views

### Sundaram's sieve in Common Lisp

I have this Sundaram's sieve to generate prime numbers up to limit in Common Lisp. ...
346 views

### Hackerrank: Computer Game (max-flow problem with integer factorization)

I am working on a coding challenge from the Hackerrank site. Given two equal-length arrays of integers, with values from 2 to 109, find the maximum number of times we can remove a pair (Ai, Bj) where ...
4k views

### Number of prime numbers between 1 and n

I came up with the following solution to find the number of prime numbers from 1 to n. I'm wondering if there is a more optimal way. ...
636 views

### Project Euler 357 prime number generator in Python 3

I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks: Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, ...
508 views

### The rusty Sieve of Eratosthenes

To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N. I have created the following code that both prints the prime ...
161 views

### Understanding RSA key generation and implementation in Java

Here is an attempt to leverage Java's BigInteger class to implement the RSA algorithm, as well as md5 and sha512 hashing functions to generate keys for what I hope to be strong cryptography. My prayer ...
739 views

### Maximum performance for Pollard's P-1 function

I am trying to find mersenne primes using python, and following the advice from https://www.mersenne.org/various/math.php, I have an intermediate step where I am using Pollard's P-1 factoring ...
6k views

### Printing prime numbers in Assembly

I am learning to code in the Assembly language for the x86 architecture. I currently know of a few registers and certain arithmetic operations like add, sub, inc, dec, mov and to check for ...
3k views

### Down to Zero II

Problem : https://www.hackerrank.com/challenges/down-to-zero-ii You are given queries. Each query consists of a single number N. You can perform 2 operations on N in each move. If N=a*b (a!=1,b!=...
1k views

### Python Prime Testing

This code seems surprisingly fast at checking if a number is prime. ...
7k views

### Project Euler #10 — Summation of primes takes forever

I have resolved the Problem presented in Project Euler #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. But this code takes too long ...
381 views

### Speeding up my implementation of Project Euler #3

Project Euler problem 3 asks for the largest prime factor of 600851475143. I have gone from 96 lines to 17 lines taking hits at this one. This is what I am left with after all of that effort: ...
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 ...
12k 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 ...
3k views

### Largest prime factor for a given number

I created a program to find the largest prime factor for a given number. The program works but unfortunately takes very long time to compute a huge number like 600851475143. How can I optimise this ...
3k views

### Prime factorization for integers with up to 9-digit long prime factors

I've become interested prime factorization since solving Project Euler problem 3 (finding the largest prime factor of 600851475143). Learning here that initializing lists with many elements to later ...
3k views

### Generating prime numbers within a range in C++

I was given a problem to find out all the prime numbers within a range. Just after I wrote the program I found numerous other codes to solve the problem. I am interested to know is my algorithm ...
921 views

### Sieve Of Erastothenes using Java

have started learning Java recently and was looking into some easy algorithms. I found the Sieve Of Erastothenes algorithm here I am trying to get better at writing good code for my solutions. Please ...
81 views

### Generating prime candidates

I'd like to generate an infinite list of prime candidates of the form 6k±1, but I'm looking for the fastest possible solution. Currently I have this: ...
39k views

### Printing the n'th prime numbers

This is an online problem. The challenge is to print the kth prime number, for each k given in the input (1 ≤ k ≤ 15000). The first line of input indicates the number of inputs on the subsequent N ...
2k views

### Project Euler 50 in Python

Project Euler, problem #50: The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime ...
3k views

### Optimization - Prime Factorizations of Numbers <= 10^7

I am using Trail Division Method with a pre-calculated list of primes to calculate the prime factorization of all numbers less than M (M <= 10^7). I am using an array of vectors of pairs. The ...
232 views

1k views

### Generating primes with Sieve of Eratosthenes

There are many problems on the Internet that require you to find prime numbers, so I decided to write a set of functions to find them. I used the Sieve of Eratosthenes for generating the primes as it ...
583 views

### Euler 35 - python solution taking too long

Here is my solution for Project Euler 35. (Find the number of circular primes below 1,000,000. Circular meaning all rotations of the digits are prime, i.e. 197, <...
174 views

### Calculate the number of primes in a range

I wrote some code to return how many prime numbers are in a specific range and what they are. It also tells you whether the number of primes is also a prime! I feel like this seems like a fairly long ...
138 views

### Find prime factors and reverse strings

I'm currently taking an introductory course to Bash at my university, and was hoping to get some peer-review from whoever might have some time. Full disclosure: the quality of the code isn't ...
485 views

### Sieve of Sundaram for Project Euler 7

This is a sequel to my previous question: Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and R I am trying to implement the Sieve of Sundaram in various languages to ...
65 views

### Finding consecutive primes matching p, p + 4, p + 6, p + 10, p + 12, p + 16

Someone asked about this question on the main StackOverflow. The full question is: Given a value N, find p such that all of ...
379 views

### Returning the prime factors of a number

I am trying to create a function prime-factors that returns the prime factors of a number. To do so, I created is-prime function,...
248 views

### Project Euler problem 50

I was just trying Project Euler problem 50. The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that ...
171 views

### Simple prime factorization program in Haskell

I'm finally learning Haskell this summer and I have a few questions about conventions. I made a simple prime factorization program which is surprisingly fast, much faster than the ones I made in C++ (...
4k views

### Printing twin primes less than a given natural number n

I have two programs doing this task correctly, but at first I'm not sure if the code is correct (I mean absence of not efficient and superfluous pieces of the code). Then, I can't choose which one is ...
1k views

### Find the 10001st prime number (in C++)

I wrote this solution for project Euler #7, to find the 10001th prime number using sieve of eratosthenes. It's really slow though. Any suggestions to improve performance (without using more complex ...
136 views

### Check sum of all primes under two million

I'm exploring ruby by writing a code that checks the sum of all prime numbers under two million. As I am still in the process of learning ruby, I'm unfamiliar with all the standards and best practices....
5k views

### Is this a good Ruby implementation of Prime Factorization?

I'm doing some practice problems on Khan Academy. The current one is Prime factorization. I came up with this: ...
6k views

### Calculating prime factors in MIPS assembly

The goal of this was to be able to enter any number and print out the prime factors of that number. Are there any shorter ways of writing this code? I'm not very familiar with low-level syntax and was ...
658 views

### Python prime number checker function

I was bored, and I was watching a sci-fi show where people were starting out during a long systems check asking each other whether numbers were prime or not, sort of passing the time as they do their ...
597 views

### Isprime Android app with kivy

I thought that developing an app in Python should be easier than learning Java. I finally got my isprime app to work but it looks ugly. When I write GUI code I ...
682 views

### A simple implementation of the principle of RSA encryption

Inspired by a Numberphile video I made a little program that shows the principles of RSA encryption and decryption. To calculate the keys I used the explanation in this link: rsa public private key ...
693 views

### A Rust crate with both main.rs and lib.rs performing primality checking

Introduction I decided to get my feet wet in Rust by going ahead an implementing a full crate with the tests, documentation, and all other accompanying stuff. This is a toy implementation of a ...