We’re rewarding the question askers & reputations are being recalculated! Read more.

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
6
votes
0answers
99 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 ...
22
votes
3answers
4k views

Checking if a number is prime in NASM Win64 Assembly

I'm just learning Assembly. This program is a simple attempt to determine if a given number is prime or not. Any advice and all topical comments on code optimization and conventions is appreciated! ...
3
votes
1answer
129 views

A prime numbers enumeration optimized for speed

I know there is this thing called "Eratosthenes" but that requires the allocation of a large array while I want to find (small) prime numbers fast, yet without needing too much memory. So I wrote ...
6
votes
1answer
140 views

Lucas Lehmer Primality Test

I have coded the Lucas-Lehmer primality test following Wikipedia's description. I used the mod 2^n - 1 suggested in the article but was wondering if there were any ...
3
votes
0answers
614 views

Miller-Rabin Primality Test Using C++ and GMP

I'm currently writing a Miller-Rabin primality test using C++ and the GNU MP Bignum Library (GMP). As I've only started learning C++ about a day ago, I'm sure this code is riddled with errors and ...
1
vote
0answers
34 views

Find parallel-base left-truncatable primes

Factorial base - representation of numbers not as sums of base_number^digit_number, but as sums of digit_number! (factorial). So 7 (decimal) is represented as 101_! in factorial base, because 7 = 6+1 =...
1
vote
2answers
76 views

Optimizing the Sieve of Eratosthenes for prime generation

I've been on a Project Euler spree and I've been solving problems and as you might know, many of them require you to use prime numbers. I've been using the following code to generate and store primes ...
11
votes
2answers
133 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 ...
8
votes
1answer
135 views

Segmented and wheel factorized prime generator in Python

I recently discovered that it is much faster to generate primes using a Sieve of Eratosthenes (SoE) with a boolean array data structure than with a heap. Since then I have been looking for fast and ...
15
votes
3answers
934 views

Wheel based unbounded sieve of Eratosthenes in Python

Answering this SO question recently, I've developed the following code (based on a well-known Active Code recipe, as discussed here): ...
2
votes
2answers
102 views

Finding the nth ugly number

I'm trying to optimize my solution to this LeetCode problem: Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the ...
2
votes
2answers
919 views

Find primes using Sieve of Eratosthenes with Python

I was Googling for a 'correct' or 'efficient' implementation of the Sieve of Eratosthenes. I found them all more complicated than what I came up with. I am by no means a Python expert, so I was ...
6
votes
2answers
149 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 ...
3
votes
1answer
64 views

Java solution to CodeChef “Surgical Strikes” challenge

I've just recently completed this programming "challenge" called surgical strikes: \$N\$ Indian Air Force fighter planes are located in different bases across the country. Each airbase is described ...
1
vote
3answers
190 views

Primality test in Python

Here is a working Python implementation of primality test. Is there something that I could change in code to achieve a better running time? For more information about algorithm see this post. ...
1
vote
0answers
55 views

Solidity: verifying primality certificates, bounty for large primes

This is my first smart contract, and it isn't finished yet, but the remaining bits are complicated enough that I'd like to make sure I'm on the right track first. My concerns are: At line 117, is the ...
5
votes
2answers
187 views

Show all primes in go

I'm trying to go through Adrian simple programming tasks; Elementary task 8 It's basically asking for an infinite loop to print every prime number as it finds it. Are there too many ...
7
votes
3answers
34k views

Efficiently determining if a number is prime

Is this the most efficient way to find if a number is prime? I can't think of a better way and it seems to run pretty quickly. ...
6
votes
1answer
115 views

Fast prime generator

I wanted to test my performance optimizing skills, and so wanted to find how fast I could get the first \$n\$ prime numbers. I limited myself to only the standard library, as I'm sure ...
6
votes
4answers
104 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 ...
3
votes
2answers
69 views

Computing the first n primes: an example from Clean Code revised for C++

I'm trying to improve on examples from Clean Code* while re-implementing them in C++. This time it's the Sieve of Eratosthenes prime-computing example from pp. 71-74. Below is the original adapted ...
3
votes
3answers
79 views

Project Euler Problem #50 Consecutive Prime Sums

Problem: Which prime, below one-million, can be written as the sum of the most consecutive primes? At the moment my code runs for over 200 seconds and was wondering how I can find a way to bring that ...
5
votes
1answer
156 views

Cached infinite prime generator

For a project I am working on, I need to use a lot of primes, frequently. To do this, I added a cache to Will Ness's prime sieve, that stores already generated primes so getting them is quick. How can ...
6
votes
1answer
112 views

Decompose any number to its prime factors raised to their respective powers

A simple code which takes the given number as input and gives all of its prime factors raised to their respective powers...works well upto 106 after that it slows down greatly for some numbers..but ...
12
votes
3answers
4k views

Python π = 1 + (1/2) + (1/3) + (1/4) - (1/5) + (1/6) + (1/7) + (1/8) + (1/9) - (1/10) …1748 Euler

I wrote this code to show that my reddit post is correct. After the first two terms, the signs are determined as follows: If the denominator is a prime of the form 4m − 1, the sign is positive; if ...
4
votes
2answers
61 views

Project Euler - Problem 3

The description of the problem is: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? Here is my solution: ...
3
votes
2answers
54 views

Trial Division Prime Generator

...
8
votes
2answers
459 views

Make Project Euler 27 solution idiomatic Ruby

I learned to program in Java and C# and in my free time I am using Ruby because it is fun. Unfortunately I have the feeling that I write Ruby code like I am making Java or C# code. I have learned to ...
3
votes
2answers
4k views

Printing all prime factors of a number input by the user

I just started teaching myself to code a few days ago using the Euler problems. I finished a variant of problem 3: print the prime factors of a number input by the user. I just want feedback and code ...
3
votes
1answer
58 views

Prime number sieve using ranges::view::ints

I wrote a simple prime number generator in C++17. The function generate_primes(max) generates all prime numbers up to max. I ...
-1
votes
2answers
74 views

Project Euler problem # 3 is this the most efficient approach in Python or can I do better?

The problem statement: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? This code takes 9 seconds!, is there a better way? ...
1
vote
3answers
78 views

Optimizing primes generating program in C++

I am writing a program to generate primes in range 1 upto 10^9 but it seems to be timing out. It implements the Sieve of Atkin I have tried optimizing my code using bitsets and pragmas. Please are ...
14
votes
3answers
1k views

Prime Sieve and brute force

Got caught up with this morning's C++ question. So I thought I would have a go. SO here is my attempt at printing the first 1001 primes. ...
5
votes
2answers
562 views

Prime Number Generator (6n + 1 or 6n - 1)

This generator is like most where it brute forces an integer: it see whether the integer is divisible by any of the primes; if so, then it's not a prime and vice versa. This though only compares ...
8
votes
2answers
832 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://...
3
votes
2answers
127 views

Sum of primes up to 2 million using the Sieve of Eratosthenes

I've solved question 10 on Project Euler using the Sieve of Eratosthenes, what can I do to optimize my code? ...
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: ...
4
votes
4answers
412 views

Find the nth term of a sequence that consists of Fibonacci and prime numbers interleaved

I have given a series problem 1,2,1,3,2,5,3,7,5.... in which the odd terms forms the Fibonacci series and even terms form the prime number series. I have to write a code in which I have to find the ...
2
votes
0answers
69 views

Parallel Miller-Rabin Prime Test in Haskell

I implemented a prime number finder using the Miller-Rabin prime test in Haskell and it seems to be working. You enter a number and it finds the next prime following that number. I also tried to make ...
5
votes
1answer
60 views

Prime Sieve and brute force #2

Based on my previous attempt. Prime Sieve and brute force Trying to make the interface simpler I have moved all the code into a class. This way I can keep track of the ...
1
vote
2answers
922 views

Clojure code for finding prime numbers

This is my Clojure code for finding prime numbers. Note: this is an advanced version which starts eliminating from i*i with step ...
7
votes
2answers
1k views

Arranging numbers in a circle such that the sums of neighbors and sums of diametric opposites are prime

I need to create a circle with numbers from 1 to n , however it is necessary to respect some rules: All numbers from 1 to n are used in the circle only once. The sum of two consecutive numbers ...
0
votes
1answer
40 views

Naïve Prime Factorization in Clojure Pt. 2

After my last review request, I decided to try and make a "tree" visualization, and thought that I could benefit from making find-prime-factors lazily produce prime ...
2
votes
3answers
209 views

Determining primality by removing select composits

Calculating many remainders for each prime and composite consumes more time. I use a factoring function to find factors of single values. When I use a factoring function to find lists of primes, I ...
5
votes
1answer
848 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
2answers
99 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++ (...
22
votes
5answers
12k views

Finding the 10001st prime

I'm solving Project Euler problem 7, which 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? Here's the ...
3
votes
1answer
159 views

Project Euler #357: Prime generating integers

Project Euler Problem 357 asks: Consider the divisors of 30: 1,2,3,5,6,10,15,30. It can be seen that for every divisor d of 30, $$d+30/d$$ is prime. Find the sum of all positive integers n ...
5
votes
1answer
67 views

Goldbach conjecture solution finder

The Goldbach conjecture says: any even number greater than two can be represented by the sum of two prime numbers. G(n) = { (p1, p2) | p1 + p2 = n, p1 and p2 are prime numbers with p1 < p2 } ...
7
votes
1answer
169 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 ...