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

### Recursion function for prime number check

I have this code: ...
179 views

...
46 views

### C: Sieve of Eratosthenes and next twin prime

I am wondering if I can get some feedback for my implementation of "Sieve of Eratosthenes" and twin prime. I followed this pseudocode. Few notes: I added ...
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: ...
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!=...
352 views

### Finding the first pair of prime numbers that have some specified difference

I tried printing the first pair of prime number in between a list of numbers with a particular difference. But my run time is still too high (for large range of numbers). I want to reduce the run time ...
119 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 ...
90 views

### Project Euler 50: Consecutive prime sum

I just finished solving Project Euler's 50th problem, but it's awfully slow. I'd like to hear your thoughts on my code's efficiency and practices. Problem Statement The prime 41, can be written as the ...
233 views

### Codewars: Prime Streaming (PG-13)

I'm timing out on Codewars' Prime Streaming kata. Below is my code: ...
283 views

### Add a number to a number to be prime number in python

The program is to get the nearest prime number to a number while adding a number. I solved the problem but I wish to optimize the code. ...
95 views

### Calculating primes: Could this be any faster?

I've ported a prime-number calculation program from primes.pyx to C++ for benchmark purpose. Since I wrote it in C++, I thought that my program would be faster than the original. However, mine took 25....
132 views

### Prime power mathematical problem in Python

I have a mathematical problem about prime power. A number $x$ can be considered a prime power if $x = p^k$ where $p$ is a prime and $k$ is a non-negative integer. For example, $81$ is a ...
80 views

54 views

### Faster way to check if number has factor of different primes than given list of primes

im trying to get the factor prime number(s) for given number if its different than the primes that i have in a list. The number have to: dividable with any of the primes in the list should not have ...
600 views

### Ugly Number - Java

I am implementing an Ugly number implementation in Java and need help to optimize the code. Maybe reduce space and/or time complexity. Ugly numbers (as per problem statement): positive numbers whose ...
2k views

### Project Euler #3 - how inefficient is my code?

So I am essentially a complete newbie to programming, and have been attempting to learn Python by completing the Project Euler problems. I haven't gotten very far, and this is my code for problem #3 : ...
626 views

### Computation for finding the largest prime factor of 600851475143 is slow

I implemented the following for Project 3 in Project Euler: ...
59 views

### Hackerrank problem -“Another Prime Problem”

I came across this issue in the problem titled: Another Prime Problem. Here's my solution with JavaScript which passed test case-1, but for other test cases it led to timeout. ...
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 ...
54 views

### Python prime finder

I wanted to try and learn multi-threading, so I thought it would be good to make a small program normally first and make it multi-threaded, so I made this prime finder. ...
140 views

### Kotlin sieve using sequences

While learning about functional programming the simple sieve example was brought up in Haskell. I wanted to try a Kotlin implementation using sequences. Are there any other quick wins without ...
55 views

### “Sum by factors” algorithm improvement

I was working on a code challenge with the following description: Given an array of positive or negative integers I= [i1,..,in] you have to produce a sorted array ...
2k views

### Prime sieve in Python

I was trying to write Sieve for the first time and I came up with this code: ...
4k views

### The next prime number in Python

I have written a solution to a DM::OJ exercise to find the next Prime Number after a given number (input). I'm seeking to optimize it so that it will run for any number up 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 ...
8k views

### Function to find two prime numbers that sum up to a given even number

The Goldbach Conjecture asserts that any even number over 2 will be the sum of exactly two prime numbers. I've created a function to find two prime numbers that add up to the number entered, but ...
6k views

### Rate my first python prime checker

I'm new to programming; I started about a week ago and started learning python. Currently, I only know some basic arithmetic operations in addition to some basic knowledge about lists, dictionaries, ...
42 views

### Prime number finder in bash

I need to learn bash at some point in the near future, so I decided to start playing around with it. This is really the first actual script that I've written and would like feedback. This finds and ...
163 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 ...
60 views

### Zen and the Sieve of Eratosthenes - Part 1: A Basic Windowed Sieve

The Sieve of Eratosthenes is one of the oldest known algorithms and yet it is still the best method for sieving prime numbers in bulk in many situations. It is brutally simple, but to make it brutally ...
410 views

### Factorising and Finding Prime numbers with list comprehension

I have created a simple code which finds the factors of any given integer. It then compares the value of the input to the range of numbers. Because a prime number can factorize into 1 and itself. Then ...
788 views

### Sum of primes under a certain number

I have tried two different methods to find the sum of primes under a certain number. However both of these methods end up taking a very long time for large numbers. How can I optimise either of these ...
281 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 ...
221 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 ...
86 views

### Prime Number Table, i.e. List<int>

I have written many variations of the Sieve of Eratosthenses, which is the fastest way to generate a large collection of primes. (@slepic asked for clarification, which I provide in an answer below. ...
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. Compiled as follows using VS2019 x64 Native Tools Command Prompt: ...
155 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 ...
881 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 ...
35 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 =...
128 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 ...
317 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 ...
196 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 ...
1k 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): ...
176 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 ...
2k 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 ...
726 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 ...
156 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 ...
385 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. ...