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
6
votes
2answers
994 views

Prime multiplication table

I am new to Ruby (1 year as hobby project on weekends) and solved a code challenge and it was not as good as they wanted. I want to know how i could make it better and how to make the structure better....
6
votes
1answer
111 views

Returns all primes p between m <= p <= n

This is my submission for the Prime Generator on SPOJ and it was accepted. Are there any improvements/changes I can make? Input: The input begins with the number \$t\$ of test cases in a ...
6
votes
1answer
64 views

Pythonic sieve of Erasthotones that saves results to file

I'd like to have some feedback on this sieve of erasthotones that I've wrote. It outputs all prime numbers up to n correctly (I've tested with the first 10k prime ...
6
votes
2answers
1k views

Fermat primality test

Here is a simple working Java implementation of primality test for Fermat numbers. Is there something that I could change in code to achieve a better running time? ...
6
votes
2answers
725 views

General primality test in C++

I have this code, which I think can be optimized even more, but I can't think of a way of optimizing the main loop to make it faster and more comprehesive. Here's the code: ...
6
votes
1answer
314 views

Sieve of Eratosthenes for prime generation

I was originally going to write this intro as just being the bare-bones "here's my problem, here are some ideas, what do you recommend" format (which I am still going to follow, mind you), but I've ...
6
votes
1answer
2k views

Generating and using a list of prime numbers

Here is some code I've created to generate and use a list of prime numbers. This is some of the first Common Lisp code I've written, and I'd be grateful for any comments regarding style and its use ...
6
votes
1answer
117 views

Decompose any number to its prime factors raised to their respective powers

A simple code which takes the given number as input and gives all of its prime factors raised to their respective powers...works well upto 106 after that it slows down greatly for some numbers..but ...
6
votes
1answer
135 views

Kotlin sieve using sequences

While learning about functional programming the simple sieve example was brought up in Haskell. I wanted to try a Kotlin implementation using sequences. Are there any other quick wins without ...
6
votes
1answer
154 views

Lucas Lehmer Primality Test

I have coded the Lucas-Lehmer primality test following Wikipedia's description. I used the mod 2^n - 1 suggested in the article but was wondering if there were any ...
6
votes
3answers
3k views

Prime factorization in Haskell

I am a Haskell beginner. Here is my function to find prime factors of a number ...
6
votes
1answer
518 views

Project Euler #10 in Swift - Summation of primes

I just finished Project Euler #10 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. I hope I learned some from ...
6
votes
1answer
341 views

Fast prime generator

I wanted to test my performance optimizing skills, and so wanted to find how fast I could get the first \$n\$ prime numbers. I limited myself to only the standard library, as I'm sure ...
6
votes
1answer
130 views

Python3 - Prime Sieve

I've implemented two prime sieves in python 3 to find all prime numbers up to an upper limit n - n exlusive. The first one is ...
6
votes
1answer
128 views

Prime numbers using wheel factorial

I have written a program to find prime numbers up to a given limit using wheel factorization of 2, 3 and 5. I would like it to work above \$10^{10}\$, but its still pretty slow. What else can I ...
6
votes
0answers
489 views

Sieve32FastV2 - A fast parallel Sieve of Eratosthenes

I’ve created a much cleaner, better designed version to my parallel sieve. I’ve implemented most of EBrown’s micro-optimizations but also revamped the code on my own (that is not in direct response ...
5
votes
4answers
1k views

Improving isPrime method

I've been doing some programming challenges and problems lately and it seems like many involve primes. I concluded that I would benefit from optimizing how I'm checking for them. Currently I'm using ...
5
votes
4answers
4k views

Project Euler 3: Largest prime factor

How can I improve my code, make it more efficient, and are there any tips you have? Project Euler 3: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the ...
5
votes
3answers
3k views

Calculate highest prime factor very slow

Sometimes when I write a Python 3.x script with too many nested loops and some big values it just takes too long to give the answer. How can I optimize my code so that it runs faster, or where should ...
5
votes
4answers
1k views

Prime factor in reverse order

...
5
votes
3answers
7k views

Summation of primes takes forever

Project Euler Problem 10 asks: "What is the sum of all prime numbers below 2 million?" How do I speed up my code? It's taking forever and I have never gotten the answer. However, I am sure that my ...
5
votes
4answers
2k views

Efficient Sum of Primes

I wrote this simple implementation of the sum of primes for the code eval Challenge Description: Write a program which determines the sum of the first 1000 prime numbers. I would like to know of a ...
5
votes
2answers
1k views

Find prime positioned prime number

This is a question from programming contest. This contest is already over. Now, all the prime numbers are arranged sequentially in ascending order. i.e:- 2, 3, 5,7...and so on. Now, your task is to ...
5
votes
3answers
11k views

BigInteger prime testing

...
5
votes
3answers
3k views

Calculating all prime palindromes from 0 to 1000 and printing the largest

I have often read about how important clear and efficient code is. Also often people talk and write about 'beautiful' code. Some hints and critic from experienced developers for the following code ...
5
votes
3answers
204 views

Snakes on a prime

The challenge is to find and print the largest palindrome prime under 1000. ...
5
votes
2answers
427 views

Slow prime finder

This program runs in about 1.65 seconds on a 1.65GHz dual core processor. I compile it with: gcc -Wall -o ./program ./program.c -lm Are there any optimizations ...
5
votes
2answers
703 views

Prime Number calculation bottleneck

Inspired by another question here: Sum of Prime numbers under 2 million, I decided to try and implement Eratosthenes' Sieve from scratch using the algorithm described in the article. ...
5
votes
2answers
728 views

Euler problem 3: largest prime factor of the number

I have been trying to learn Python and just solved Euler Problem 3: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I am looking ...
5
votes
4answers
2k views

Find the nth prime number

It's a long time since I've written a Sieve of Eratosthenes (about 3 decades, I think, in ZX Basic). So I decided to revisit in the light of experience. Rather than allocating a vector of unknown ...
5
votes
4answers
2k views

Any better way to solve Project Euler Problem #5?

Here's my attempt at Project Euler Problem #5, which is looking quite clumsy when seen the first time. Is there any better way to solve this? Or any built-in library that already does some part of the ...
5
votes
3answers
141 views

Outputting prime numbers in given ranges

I coded an algorithm which shows prime numbers in the ranges provided by the user. The first line states the number of test cases. Example: INPUT 2 1 10 1 5 ...
5
votes
2answers
266 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 ...
5
votes
3answers
199 views

Custom Prime Sieve

I've come up with a prime number finder I call the "Progressive Sieve". I wouldn't doubt it if this has already been thought of. Anyway, here is the idea, an implementation in C#, and benchmarks: ...
5
votes
3answers
797 views

Prime less than N that is a sum of the most consecutive other primes

Here's a Python implementation of the Sieve of Eratosthenes: ...
5
votes
2answers
2k views

Prime generator program SPOJ time limit exceed

Problem Statement Input The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-...
5
votes
3answers
598 views

Ugly Number - Java

I am implementing an Ugly number implementation in Java and need help to optimize the code. Maybe reduce space and/or time complexity. Ugly numbers (as per problem statement): positive numbers whose ...
5
votes
3answers
683 views

Project Euler #47: Distinct primes factors

I have solved Project Euler's problem number 47, which reads: The first two consecutive numbers to have two distinct prime factors are: 14 = 2 × 7 15 = 3 × 5 The first three ...
5
votes
2answers
1k 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, ...
5
votes
2answers
984 views

Project Euler #10 - sum of primes below two million

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. ...
5
votes
3answers
965 views

Project Euler Problem #10

I've read other solutions about solving the 10th problem for Project Euler (finding the sum of all prime numbers under 2,000,000) but I wanted to try it on my own using the Sieve of Eratosthenes ...
5
votes
1answer
762 views

Project Euler #10 - summation of primes

(From Project Euler) The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. Can someone please help me improve this code? ...
5
votes
2answers
4k views

Finding prime numbers in a range

Finding the prime numbers between two given integers in the minimum number of comparisons: ...
5
votes
2answers
664 views

Prime Number Generator (6n + 1 or 6n - 1)

This generator is like most where it brute forces an integer: it see whether the integer is divisible by any of the primes; if so, then it's not a prime and vice versa. This though only compares ...
5
votes
5answers
1k 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 ...
5
votes
2answers
889 views

Find the next prime number — flow control of nested `for` loops

This code works perfectly, but it bothers me. Having a labeled, nested for loop, with a true condition, a ...
5
votes
3answers
2k views

Finding the Nth prime

I'm going through some of the problems over on exercism and we were asked to write a program that finds the nth prime. I know Ruby has a Prime class that handles that but the exercise doesn't allow us ...
5
votes
1answer
2k views

Sieve of Eratosthenes - Standard and Optimized implementation

I am a Java developer who is taking Python for the first time. I'm sure this is not at all elegant since I am thinking more in C syntax. ...
5
votes
3answers
936 views

Prime number util class

A prime number util, which provides 3 APIs - find the nth prime, find the next prime, and find all primes up to n. I must admit this code has been influenced a lot by discussions here. I'm looking ...
5
votes
2answers
451 views

Show all primes in go

I'm trying to go through Adrian simple programming tasks; Elementary task 8 It's basically asking for an infinite loop to print every prime number as it finds it. Are there too many ...

1
3 4
5
6 7
14