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
4answers
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 ...
8
votes
4answers
10k views

Fast Number Factorization in Python

Here's my implementation to factorize a positive integer: ...
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
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
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 ...
8
votes
2answers
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 ...
8
votes
1answer
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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 ...
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
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 ...
8
votes
4answers
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 ...
8
votes
2answers
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 ...
8
votes
2answers
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 ...
8
votes
1answer
234 views
8
votes
2answers
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 ...
8
votes
1answer
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 ...
8
votes
1answer
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
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> ...
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
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. ...
7
votes
3answers
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 ...
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
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
562 views

Eratosthenes' and Sundaram's prime sieves in Python

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

Fermat Factorization

Please review my implementation of Fermat's Factorization. ...
7
votes
2answers
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 ...
7
votes
1answer
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 ...
7
votes
2answers
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 ...
7
votes
1answer
138 views

Strange performance difference

For exercise, I wrote this code: ...
7
votes
1answer
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. ...
7
votes
1answer
321 views

Sundaram's sieve in Common Lisp

I have this Sundaram's sieve to generate prime numbers up to limit in Common Lisp. ...
7
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 ...