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
2
votes
3answers
72 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 ...
1
vote
1answer
166 views

Codewars: Prime Streaming (PG-13)

I'm timing out on Codewars' Prime Streaming kata. Below is my code: ...
6
votes
4answers
330 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 ...
7
votes
2answers
274 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. ...
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!=...
1
vote
2answers
94 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....
2
votes
2answers
118 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 ...
-5
votes
1answer
71 views

Find pair of adjacent prime numbers in a two-dimensional array

Does anybody know how to find pair of adjacent prime numbers in two-dimensional array, quicker than this? I'm talking especially about this part which looks for adjacent numbers not about function ...
2
votes
1answer
53 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 ...
5
votes
3answers
591 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 ...
8
votes
2answers
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 : ...
4
votes
1answer
612 views
2
votes
1answer
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. ...
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 ...
1
vote
1answer
53 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. ...
6
votes
1answer
132 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 ...
1
vote
0answers
49 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 ...
13
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: ...
2
votes
2answers
3k 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 ...
6
votes
2answers
64 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 ...
4
votes
2answers
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 ...
13
votes
8answers
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, ...
0
votes
2answers
40 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 ...
7
votes
1answer
160 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 ...
1
vote
0answers
57 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 ...
3
votes
1answer
256 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 ...
1
vote
2answers
281 views
4
votes
4answers
781 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 ...
6
votes
2answers
173 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 ...
3
votes
3answers
215 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 ...
4
votes
1answer
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. ...
23
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. Compiled as follows using VS2019 x64 Native Tools Command Prompt: ...
6
votes
1answer
154 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
861 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
109 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
255 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
183 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
982 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
158 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
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 ...
6
votes
2answers
607 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
142 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 ...
1
vote
3answers
309 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
62 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
398 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
35k 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
270 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
143 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
74 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 ...

1
2 3 4 5
14