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
4
votes
2answers
63 views

Primality Test Refactoring

I devised a new primality test isPrimeNumber() below which determines if 1000000007 is prime. It works fine but the code looks unprofessional in my opinion. Is there any way to refactor it to make it ...
3
votes
3answers
105 views

Why is this Segmented Prime Sieve so fast?

The idea of a prime sieve is fascinating - but it has to be segmented to increase the locality of the code if you want it to be fast. Walish's segmented_sieve.cpp (see below)showed me that it works - ...
8
votes
2answers
298 views

Calculate all the prime numbers between two given numbers

I've made an application that calculates all the prime numbers between two given numbers and prints then into a .txt document... anything I can improve? ...
2
votes
4answers
90 views

Is this an efficient/correct way to get largest Prime factor?

Is this an efficient way to get the largest prime factor of a given number? Other solutions I found involved nested algorithms. ...
3
votes
1answer
50 views

Prime number sequence supporting repeated iteration

I'm a long-time Java programmer, but recently I decided to give Kotlin a try. So far, I'm loving the language features, it feels much more expressive than what I'm used to. As practice, I wrote this ...
1
vote
0answers
56 views
3
votes
0answers
52 views

Performance issue regarding Project Euler #60 in Scheme

I solved Project Euler #60: The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 ...
2
votes
1answer
79 views

Prime numbers with array and OpenMP in C

...
20
votes
4answers
5k views

Why is my Sieve of Eratosthenes using generators so slow

This is my prime sieve based on the Sieve of Eratosthenes. ...
-3
votes
2answers
184 views
4
votes
1answer
48 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 ...
9
votes
2answers
130 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 ...
3
votes
3answers
107 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 ...
7
votes
4answers
359 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 ...
8
votes
2answers
295 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. ...
1
vote
2answers
96 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....
4
votes
2answers
145 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 ...
2
votes
1answer
58 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 ...
2
votes
1answer
66 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. ...
1
vote
1answer
62 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. ...
1
vote
0answers
69 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 ...
6
votes
2answers
66 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 ...
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
45 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 ...
2
votes
1answer
295 views

Codewars: Prime Streaming (PG-13)

I'm timing out on Codewars' Prime Streaming kata. Below is my code: ...
1
vote
0answers
71 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
667 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 ...
0
votes
2answers
1k views

Recursion function for prime number check

I have this code: ...
4
votes
4answers
798 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 ...
4
votes
1answer
92 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. ...
-5
votes
1answer
101 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 ...
7
votes
2answers
469 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
243 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 ...
7
votes
1answer
171 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
36 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 =...
11
votes
2answers
463 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
246 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 ...
2
votes
2answers
195 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 ...
1
vote
2answers
140 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 ...
3
votes
1answer
195 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
577 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
70 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 ...
6
votes
4answers
380 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
75 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
131 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 ...
7
votes
2answers
863 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 ...
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 ...
3
votes
2answers
61 views

Trial Division Prime Generator

...
4
votes
2answers
68 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: ...
0
votes
2answers
92 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
2 3 4 5
14