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
7
votes
1answer
228 views

Fermat Factorization

Please review my implementation of Fermat's Factorization. ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
138 views

Strange performance difference

For exercise, I wrote this code: ...
7
votes
1answer
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. ...
7
votes
1answer
331 views

Sundaram's sieve in Common Lisp

I have this Sundaram's sieve to generate prime numbers up to limit in Common Lisp. ...
7
votes
1answer
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 ...
7
votes
1answer
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. ...
7
votes
2answers
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, ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
1answer
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 ...
7
votes
2answers
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!=...
7
votes
4answers
1k views

Python Prime Testing

This code seems surprisingly fast at checking if a number is prime. ...
6
votes
6answers
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 ...
6
votes
6answers
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: ...
6
votes
4answers
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 ...
6
votes
2answers
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 ...
6
votes
6answers
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 ...
6
votes
2answers
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 ...
6
votes
4answers
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 ...
6
votes
3answers
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 ...
6
votes
1answer
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: ...
6
votes
2answers
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 ...
6
votes
4answers
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 ...
6
votes
5answers
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 ...
6
votes
1answer
232 views

Counting primes in a range whose digits are all prime

Codewars Kata: Given integers a and b, count all primes p where a ≤ p < b and the digits of p are all prime. b may be as large as 107. To start with, I hardcoded all valid 1903 primes in \$[1, 10^...
6
votes
2answers
212 views

Divisor game cheating aid

This code outputs the smallest number with more divisors than the input: ...
6
votes
2answers
331 views

Quadratic Primes - Project Euler 27

Project Euler Problem 27 Euler discovered the remarkable quadratic formula: \$n^2 + n + 41\$ It turns out that the formula will produce \$40\$ primes for the consecutive values \$n = 0\$...
6
votes
3answers
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 ...
6
votes
2answers
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, <...
6
votes
4answers
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 ...
6
votes
2answers
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 ...
6
votes
3answers
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 ...
6
votes
2answers
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 ...
6
votes
2answers
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,...
6
votes
2answers
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 ...
6
votes
2answers
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++ (...
6
votes
2answers
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 ...
6
votes
2answers
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 ...
6
votes
1answer
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....
6
votes
1answer
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: ...
6
votes
1answer
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 ...
6
votes
5answers
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 ...
6
votes
1answer
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 ...
6
votes
2answers
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 ...
6
votes
1answer
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 ...
6
votes
1answer
180 views

Generating smooth numbers in Haskell

I wrote a smooth function that returns a list of all smooth numbers below a certain limit from a list of prime: ...
6
votes
1answer
153 views

C the sum of primes

The challenge is to calculate the sum of the first 1000 primes. The code applies a sieve thanks to past answer, here, and works but I wonder about the flexibility of this solution. ...

1 2 3
4
5
14