# 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
13k views

### Find prime numbers under N

I'm using the Sieve of Eratosthenes to find primes numbers under N. Is there any performance problems you see with my approach? I used the LinkedList<Integer> ...
510 views

### Prime sieve for all primes up to a number

As a beginner to C++, I wanted to make something using what I was learning, so I did this to learn about arrays. This implements the Sieve of Eratosthenes to find the primes up to a limit. I didn't ...
8k views

### Program for finding Fibonacci primes

I think it could have been designed with more object orientation. I don't like how one of my methods calls another from within the method, but I wasn't sure how to return the result because it is a ...
12k views

### Yet another prime number generator

The question asked to find all the prime numbers within a particular range. The way I approached this was to loop through each of the numbers within the range and for each number check whether it's a ...
3k views

### Project Euler 407: Is there any more optimal way to solve this idempotent equation (modulo n ring)?

Project Euler problem 407: If we calculate a2 mod 6 for 0 ≤ a ≤ 5 we get: 0, 1, 4, 3, 4, 1. The largest value of a such that a2 mod 6 = a is 4. Let's call M(n) the largest value of a < n ...
779 views

### Prime generator

I'm coming from a Python background(look at indentation :) ) and trying to learn basics of C++. I wrote a simple prime generator, I know there is better algorithms, but I want advices about coding ...
699 views

### Ten thousand and first prime checker takes a very long time

I am attempting problem 7 on Project Euler. I have come up with this solution which works fine for finding smaller nth prime numbers, but really lags when it comes to higher nth prime numbers. I am ...
840 views

### Looking for primes with all-different digits

I recently answered a question on Mathematics Stack Exchange, where I used a small Python program to check the following : For all 6-digit numbers, with all digits being different, choosing the ...
4k views

### Checking for circular primes - Project Euler Problem 35

I have been trying to solve Project Euler problem number 35. The problem is to find: How many circular primes are there below one million? A circular prime is a prime where all the rotations of ...
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. ...
2k views

### Prime Number Generator in Swift

I would like to make (or improve my function) a function that returns an array of integers containing all the prime numbers from 2...n that can execute as quickly ...
351 views

### Project Euler+ #35 - Summing circular primes less than N

Overview The following code is a solution for a Project Euler+ problem on Hackerrank. A circular prime is a prime number whose rotations are also prime. For example, 197 is a circular prime since it ...
264 views

### Summation of primes for large inputs

I'm doing a problem from Project Euler to find the sum of all primes under two million. My code manages to get a pretty good result for small inputs, but when trying inputs like million or two it ...
244 views

### Find “prime polynomials” for a user's given prime, bounds, and degree

Very amateur programmer and first-time poster here. The program I wrote asks the user for a prime number, a lower and upper bound, and a degree (all of these are integers). I want to generate a list ...
259 views

### Prime generator from one to n

My code calculates primes from one to n. I have verified that the code always produces all the primes in that range correctly. Are there any optimizations that I can make? Are there any bad ...
2k views

### Generating very large prime numbers and their generator modulo N in php

I recently came up with the idea to attempt generating ungodly large prime numbers and their generators modulo N in php. I don't know much about number theory and just wanted to get some comments to ...
487 views

### Prime factors and perfect square

I want to convert an integer to a perfect square by multiplying it by some number. That number is the product of all the prime factors of the number which not appear an even number of times. Example ...
170 views

### Searching for pairs of integers that satisfy primality and divisibility conditions

I wrote a program in Python 3 to check all tuples of the form (s,t) where s and t are ...
241 views

### A type for prime numbers

I have recently discovered that in type theory there is a concept of a "predicate type" which is a type $A$ formed out of all members of the underlying type $U$ that satisfy a given predicate ...
271 views

### Primality test program

I am fairly new to programming and even newer to C++ but I am currently in a class for scientific computing, and our task from two weeks ago was to improve the speed of a primality test program. I ...
467 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 ...
237 views

...
458 views

### Postponed Prime Sieve in Swift

Motivated by this question, I looked out for other "infinite prime generators", i.e. functions which produce the list of prime numbers in increasing order and do not have an a-priori upper limit (such ...
474 views

### Prime generator for SPOJ

I have written code to solve the prime generator problem. I am given an input which contains in the first line the number of test cases, and for each test case, I am given a range and I have to print ...
1k views

### Remake of factoring/prime factorization calculator

Background info on factoring and prime factorization. I've remade this program from my first attempt, and I'm sure it can still be improved. My questions: These calculations should only be done ...
1k views

### Listing the first five perfect numbers in MIPS assembly

I've done some programming in the past, but I'm new to MIPS, which I'm trying to learn on my own. This program lists the first five perfect numbers. It uses the Lucas-Lehmer and Miller-Rabin primality ...
27k views

### Prime factorization of a number

I'm trying to learn Python through the excellent online book Dive Into Python 3. I have just finished chapter 2 about data types and felt like trying to write a program on my own. The program takes an ...
194 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 ...
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 : ...
12k views

### Checking if a number is prime

Is there a better way to check if a number is a prime? ...
4k views

### Sum of the digits is prime or not

Puzzle Description: A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky? How can I ...
2k views

### A fast approach to prime number sieving (non-threaded array)

I am posting this question for input on comparisons between other sieving methods and opinions on what I have discovered. I believe this might be the fastest (singular, non-threaded) array ...
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. ...
393 views

### Modified Sieve of Eratosthenes has very long runtime

I am slowly moving through Project Euler, and have reached problem #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. I did a naive ...
1k views

### Read numbers until a prime is entered then print non-primes

I'm a beginner at C#. I just want to know what is the C# way to do this by its convention and a better algorithm as well. ...
2k views

### Sum the exponents of the prime factors of a number

My goal is to find the sum of the exponents of the prime factors of an integer. I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though): Runtime ...
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 ...
2k views

### Efficient prime factorization for large numbers

I've been working on a little problem where I need to compute 18-digit numbers into their respective prime factorization. Everything compiles and it runs just fine, considering that it actually works, ...
651 views

### Eratosthenes' and Sundaram's prime sieves in Python

I recently started playing with Python. What can I do better? ...
564 views

### Making prime (sieve) code faster and able to run on big numbers

For an input triple (a, b, c), the task is to count the number of integers in the inclusive range [a, b] which have c distinct prime factors. This entails factoring each of the numbers in the range [a,...
1k views

### Project Euler #3 (Largest prime factor) in Swift

As mentioned in Project Euler #2 in Swift, I intend to work my way through Project Euler using Swift to make sure there aren't any tricks I'm missing. This is the problem statement for #3: The ...
350 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 ...
3k views

### alternating Fibonacci and prime series

The task is to print the following series 1 2 1 3 2 5 3 7... The elements at odd positions are Fibonacci series terms and the elements at even positions are ...
577 views

### Finding circular primes

I'm coding for a project euler question and every now and then, the question will demand a program that is efficient even when doing brute force. Which I struggle with. Below is a piece of code for ...
757 views

### A more optimized way of finding prime factors

I've solved Project Euler #3, but solving the same in Hacker Rank which has time constraint of < 4 seconds doesn't work. I've tried using the square root solution for speeding up but it fails. ...
489 views

### Project Euler #7 - 10001st prime

I just finished Project Euler #7 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. By listing the first six prime ...
634 views

### Counting Fermat witnesses and liars

We were asked to implement a program that calculates the number of Fermat witnesses and liars for odd numbers greater 1. This involves Fermat’s little theorem. Fermat’s little is used to identify ...
375 views

### Printing factors and prime factors of a number

I am a 46 year young newbie trying to learn programming for fun and adventure. I do this in my free time. Some very nice gentlemen on stackoverflow have sent me here. I wish that someone could review ...