# 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.

638 questions
Filter by
Sorted by
Tagged with
765 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 ...
10k views

### Fast Number Factorization in Python

Here's my implementation to factorize a positive integer: ...
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 ...
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 ...
291 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 ...
253 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 ...
214 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 ...
197 views

### Largest Prime Factor redux

There have been a number of questions asking for comments on code for the Project Euler problem to compute the largest prime factor of a number. A primary intent of this task is to find the factor as ...
258 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 ...
446 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 ...
163 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 ...
262 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 ...
460 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 ...
234 views

...
991 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 ...
140 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 : ...
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> ...
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 ...
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. ...
378 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. ...
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, ...
562 views

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

I recently started playing with Python. What can I do better? ...
836 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 ...
529 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 ...
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 ...
2k 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 ...
546 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 ...
735 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. ...
445 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 ...
585 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 ...
367 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 ...
3k views

### Goldbach’s Conjecture in Python

Input Format Input starts with an integer n (1 ≤ n ≤ 100) indicating the number of cases. The following n lines each contain a test case of a single even number x (4 ≤ x ≤ 32000). Output Format For ...
2k views

### Test a number for primality and return smallest divisor different from 1 if it’s is composite

In this exercise we were asked to test a number for primality and print the results. Additionally – in the case the number is composite – the smallest divisor different from 1 should be printed out. ...
225 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 ...
428 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 ...
221 views

### Fermat Factorization

Please review my implementation of Fermat's Factorization. ...
256 views

### Sieve of Eratosthenes and twin prime finder

I made this program to find primes and twin pairs. I'd like feedback on anything from formatting to content to technique. In short: how would this be different if it was written by an experienced ...
128 views

### Sum of primes in given range in Go

This piece of code calculates the sum of all prime numbers below 1 million. It stood out to me that the Ruby script is around 20% faster. I know that Go should be faster just for being a compiled ...
367 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 ...
138 views

### Strange performance difference

For exercise, I wrote this code: ...
462 views

### Prime Numbers Store

Let's say we need to create a store for selling prime numbers. Users enter the store and ask to buy a number. If the number asked is a prime number, 1.1. then it's either available for sale 1.2. ...