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
8
votes
7answers
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> ...
8
votes
1answer
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 ...
8
votes
6answers
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 ...
8
votes
4answers
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 ...
8
votes
1answer
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 ...
8
votes
4answers
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 ...
8
votes
5answers
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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. ...
8
votes
1answer
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 ...
8
votes
3answers
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 ...
8
votes
2answers
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 ...
8
votes
1answer
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 ...
8
votes
2answers
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 ...
8
votes
3answers
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 ...
8
votes
1answer
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 ...
8
votes
4answers
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 ...
8
votes
1answer
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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 ...
8
votes
1answer
237 views
8
votes
2answers
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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 ...
8
votes
1answer
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 ...
8
votes
3answers
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 ...
8
votes
1answer
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 ...
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 : ...
7
votes
4answers
12k views

Checking if a number is prime

Is there a better way to check if a number is a prime? ...
7
votes
7answers
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 ...
7
votes
5answers
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 ...
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. ...
7
votes
3answers
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 ...
7
votes
6answers
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. ...
7
votes
2answers
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 ...
7
votes
2answers
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 ...
7
votes
4answers
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, ...
7
votes
4answers
651 views

Eratosthenes' and Sundaram's prime sieves in Python

I recently started playing with Python. What can I do better? ...
7
votes
1answer
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,...
7
votes
2answers
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 ...
7
votes
4answers
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 ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
1answer
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. ...
7
votes
2answers
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 ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
4answers
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 ...
7
votes
4answers
3k 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. ...

1 2
3
4 5
14