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.

635 questions
Filter by
Sorted by
Tagged with
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
94 views

### Prime factorization - C

After learning prime factorization today, below is the C code written, ...
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 ...
735 views

### Prime factoring function using recursion

As a programming exercise, I decided to make a prime factoring function using recursion: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
844 views

### Calculate prime numbers

This is a program to calculate the largest prime number. Are there any possible improvements in style/speed/accuracy? ...
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 ...
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. ...
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!=...
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 ...
925 views

### Python Prime Testing

This code seems surprisingly fast at checking if a number is prime. ...
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 ...
1k views

### Lucas sequence implementation

Could you suggest any improvements in this Lucas sequence's implementation: ...
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? ...
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 ...
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 ...
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; ...
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 ...
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 +...
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 ...
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 ...
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. ...
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? ...
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 ...
275 views

### Simple Factor Class

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

### First n primes optimization

Pretty standard. Generates the first n primes, input via a scanner. ...
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 ...
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 ...
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 ...
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 ...
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. <...
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 ...
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 ...
67 views

...