We’re rewarding the question askers & reputations are being recalculated! Read more.

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
14
votes
1answer
548 views

Large Number Limit Extravaganza

I am writing a program that computes $$n-n \cdot \left(\prod_{i=1}^n (1-\frac{1}{p_i})\right)$$ which is rewritten in my code as: $$\left(1-\left(\prod_{i=1}^n(1-\frac{1}{p_i})\right)\right) \cdot ...
6
votes
1answer
166 views

Generating smooth numbers in Haskell

I wrote a smooth function that returns a list of all smooth numbers below a certain limit from a list of prime: ...
3
votes
1answer
121 views

Prime Factors (32 bits, without Sieve)

I wrote this prime factors program as a programming exercise. Any comments or constructive criticisms are welcome. One question: prime[] is an array which stores the number's prime factors and ...
1
vote
1answer
388 views

Finding numbers divisible by primes in a given range

The problem statement (Codeforces# 385C) is this: We are given a sequence of \$n\$ numbers, i.e. \$x_i\$ and \$m\$ queries to find how many of these are divisble by primes between two given numbers ...
4
votes
2answers
745 views

Simple prime number search with trial division

I made a primality tester with trial division. I'm trying to make it as fast as possible and have reached the point now where I'm out of ideas. I use the generator approach and not lists because I ...
1
vote
1answer
88 views

Quicklyish finding primes by trial division

I ask because it seems to be taking waaaay more space/time than it should. Also, I know that if I want to be super efficient I should use Java's BitSet and a Sieve of Eratosthenes, but I wrote it like ...
5
votes
2answers
911 views

FASM assembly: Write a program which checks if a number is a prime number

Coming from high-level languages like PHP and JavaScript, I'm doing an Assembly course on Udemy. Yesterday I tried to implement the following task: Write a program that takes a number m as input, ...
11
votes
4answers
2k views

Project Euler Problem 35: counting circular primes below 1 million

Project Euler Problem 35 asks: The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime. How many circular primes are there ...
1
vote
1answer
94 views

Prime factorization - C

After learning prime factorization today, below is the C code written, ...
-1
votes
1answer
500 views

Largest prime factor of a given number

I'm solving Problem 3 in Project Euler: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143? Most answers I found made use of array to ...
3
votes
3answers
735 views

Prime factoring function using recursion

As a programming exercise, I decided to make a prime factoring function using recursion: ...
2
votes
2answers
2k views

Infinite prime generator

This code acts as an infinite generator of prime numbers. As new prime numbers are found, they are added to a set. Then, a number x is found to be prime if none of the numbers in the prime set are ...
5
votes
2answers
264 views

Yet Another, Another Prime Generator

Yes, I realize there are many, many, many, many, many, prime generators on the Code Review SE. However, I have been unable to find any using this method for generating primes inside a vector, so I ...
2
votes
0answers
179 views

Mersenne Prime Checker using Lucas-Lehmer Formula

Previously I created a C# script that used trial division to check to see whether or not certain Mersenne numbers were prime. Since these numbers are so big, I employed some math shortcuts to reduce ...
12
votes
2answers
3k views

Project Euler #10 in C++ (sum of all primes below two million)

Project Euler Problem 10 asks for the sum of all the primes below two million. I'm creating a list of primes and keep checking any new number for divisibility with only prime numbers. I thought it ...
2
votes
2answers
560 views

Mersenne Primes Generator in C#

I've made a program in C# that generates Mersenne numbers starting from the current largest known Mersenne prime. It then calculates the modulo between those numbers and smaller ones starting from 3 ...
1
vote
1answer
118 views

Custom Sieve of Eratosthenes

I'm trying to improve my code to find all the prime numbers within a set range as fast as possible, and I am trying to make it even faster. On my github page here, I have some optimization settings ...
4
votes
1answer
966 views

List of all prime factors of a number, including repeats

This code will return a list of the prime factors of n, and the prime factors are repeated so that the product of the list is equal to n. ...
4
votes
2answers
165 views

Sieving for prime numbers

I wanted to implement the Sieve of Erathosthenes up to int.MaxValue in C#. No object is allowed to exceed 2Gb so you can't allocate a ...
1
vote
4answers
844 views

Calculate prime numbers

This is a program to calculate the largest prime number. Are there any possible improvements in style/speed/accuracy? ...
5
votes
5answers
874 views

Project Euler #3 in C# - largest prime factor

I just started doing the Project Euler challenges and right now I'm on Challenge #3 - The largest prime factor of 600851475143. I wrote some code and tried to optimize it based on some other Stack ...
3
votes
1answer
316 views

Project Euler #58: Primes along the diagonals of a square spiral

I am working on Project Euler Problem 58: Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed. ...
6
votes
1answer
2k views

Down to Zero II

Problem : https://www.hackerrank.com/challenges/down-to-zero-ii You are given queries. Each query consists of a single number N. You can perform 2 operations on N in each move. If N=a*b (a!=1,b!=...
1
vote
2answers
195 views

Project Euler Problem #3 in Java - Largest Prime Factor

I have solved the problem and it gives me the right output when the BigInteger has the smaller value, however it kept running for more than 20 minutes with the ...
7
votes
4answers
925 views

Python Prime Testing

This code seems surprisingly fast at checking if a number is prime. ...
3
votes
1answer
530 views

Efficient Prime Sieve - Haskell

I'm new to Haskell, and am trying to learn the basics with a simple function that will calculate the list of primes up to a given value (using the Sieve of Eratosthenes). Here is my code so far, which ...
3
votes
3answers
1k views

Lucas sequence implementation

Could you suggest any improvements in this Lucas sequence's implementation: ...
2
votes
3answers
2k views

Finding out the prime factors of a number

This finds the prime factors of a number given in a variable. Is it efficient or in need of improvement? ...
3
votes
2answers
269 views

Testing Goldbach's Conjecture hypothesis

A book1 that I'm reading states Goldbach's conjecture as follows: Every even integer > 2 could be represented as a sum of two prime numbers. Every integer > 17 could be represented as a sum of ...
3
votes
2answers
348 views

Postponed Prime Sequence in Kotlin

Following my previous unbounded prime generator and a followup by Martin R, I've tested the waters in Kotlin by making an unbounded sieve. To quote Martin R's wonderful explanation of the base ...
3
votes
1answer
147 views

SICP exercise 1.28 - miller-rabin primality test part II

This is a follow-up to SICP exercise 1.28 - miller-rabin primality test. Exercise 1.28: One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; ...
2
votes
1answer
340 views

Generating numbers that are a product of consecutive primes

I have implemented a correct but horribly coded solution to Project Euler Problem 293. An even positive integer N will be called admissible, if it is a power of 2 or its distinct prime factors ...
1
vote
1answer
87 views

Project Euler 12 (triangle numbers), solved using functools.reduce() and looping

I have solved problem 12 on Project Euler website, which reads: The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 +...
2
votes
2answers
2k views

Simple Input Text Analysis

I've started learning java. I've written a small program I've done in C before. It's simple input analysis. If there is number, program checks if number is prime. Then write number: (value of input ...
1
vote
2answers
909 views

Multithreaded brute force prime generator

A number is a prime when it is divisible by 1 and the number itself. To check if a given number is a prime we can divide the number by primes which are less than the square root of that number. If ...
3
votes
1answer
67 views

Stateful prime_numbers class for searching and storing primes

Title says the biggest part. The class is designed to be used to search for very big prime numbers, hence the element type is templated. The performance, neither in space nor time, is considered. ...
3
votes
3answers
3k views

Check if given number can be expressed as sum of 2 prime numbers

Similar problem: Sum Of Prime I've done the given problem in roughly \$\mathcal{O}(n\sqrt{n})\$. How can I improve this algorithm? ...
2
votes
2answers
1k views

Find prime numbers from 1 to 100

Create a program to find all the prime numbers between 1 and 100. One way to do this is to write a function that will check if a number is prime (i.e., see if the number can be divided by a prime ...
1
vote
1answer
275 views

Simple Factor Class

I have a class which lazily factors numbers. It provides the user with these methods: getFactors returns a ...
3
votes
3answers
431 views

First n primes optimization

Pretty standard. Generates the first n primes, input via a scanner. ...
1
vote
2answers
80 views

Another Python prime-listing algorithm

I wrote a small program in Python that finds primes (how original) up to some limit. I tried to produce very clean code, so I'd be vary grateful if you could point out any improvement I could do to ...
7
votes
2answers
426 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 ...
5
votes
1answer
847 views

Find the 10001st prime number (in C++)

I wrote this solution for project Euler #7, to find the 10001th prime number using sieve of eratosthenes. It's really slow though. Any suggestions to improve performance (without using more complex ...
2
votes
1answer
727 views

Unbounded Sieve of Eratosthenes in Swift

I've spent a while teaching myself Swift, and decided to take on the challenge of writing an unbounded Sieve of Eratosthenes to challenge myself. This is actually the first time I've written an ...
1
vote
3answers
192 views

Finds all the prime numbers up to n using a strange pattern

Here's an odd pattern I found for sieving out composite numbers to find primes. I wrote it myself, originally thinking I made an indexing error, but it turned out to work after removing squares. <...
7
votes
2answers
252 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 ...
3
votes
1answer
150 views

The Miller-Rabin Primality Test in Clojure

I am new to clojure and I wanted to test out my skills by taking an existing implementation written in Python and writing it in Clojure. Concerns My main concerns are where I use ...
1
vote
1answer
67 views

Constantly calculate blocks of prime numbers

...
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 ...
1
vote
0answers
90 views

Computation of primality

I believe I have achieved computation of primality! That is, the computation of prime numbers. The code I am about to post will give you every prime there is, in order, starting with 2. Can we call ...