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
0answers
108 views

Understanding RSA key generation and implementation in Java

Here is an attempt to leverage Java's BigInteger class to implement the RSA algorithm, as well as md5 and sha512 hashing functions to generate keys for what I hope to be strong cryptography. My prayer ...
6
votes
0answers
398 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
6answers
7k views

Project Euler #10 — Summation of primes takes forever

I have resolved the Problem presented in Project Euler #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. But this code takes too ...
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
3k 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 ...
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
2answers
2k views

Prime factorization for integers with up to 9-digit long prime factors

I've become interested prime factorization since solving Project Euler problem 3 (finding the largest prime factor of 600851475143). Learning here that initializing lists with many elements to later ...
5
votes
3answers
10k 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
197 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
693 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
633 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
138 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
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 ...
5
votes
3answers
195 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
765 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 <= ...
5
votes
2answers
934 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
873 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
855 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
681 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
569 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
3answers
576 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
5answers
897 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
886 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
906 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
142 views

BitSet wrapper to act as a sieve abstraction

This is a BitSet wrapper class to act as a Sieve abstraction for a prime calculator. Review for performance and Java/Java 8/Guava best practices. ...
5
votes
1answer
403 views

Prime number calculator using Sieve of Eratosthenes

I've been writing this prime number calculator, and I've gotten it pretty quick in comparison to most I've seen knocking about. This one uses the Sieve of Eratosthenes approach, and I've optimised the ...
5
votes
1answer
4k views

Is this a good Ruby implementation of Prime Factorization?

I'm doing some practice problems on Khan Academy. The current one is Prime factorization. I came up with this: ...
5
votes
4answers
7k views

Generating a list of primes of a given length

After considerable effort, I've come up with the following code to generate a list of primes of a given length. I would be very interested to see how an experienced coder would modify my code to make ...
5
votes
2answers
200 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 ...
5
votes
1answer
858 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 ...
5
votes
1answer
596 views

Number of divisors of a factorial

I was solving the DIVFACT problem from Sphere Online Judge: Given a number, find the total number of divisors of the factorial of the number. Since the answer can be very large, print the answer ...
5
votes
1answer
661 views

Prime number generator

I have a created small program that prints a sequence of prime numbers. Based on the origin code in here. How can I improve this code? ...
5
votes
1answer
2k views

“Is a number prime?”

I've come up with a very efficient way of finding if a number is prime, using TI-BASIC for use with TI-83/84/+/SE calculators. I am trying to optimize it however possible. ...
5
votes
2answers
802 views

Submitting a Java program which implements the Sieve of Eratosthenes

I would like some feedback on a Java program which implements the Sieve of Eratosthenes to find prime numbers. Some of the 'features' I've included in the program include: It uses a ...
5
votes
2answers
1k views

Prime Number Speed

I know prime number programs have been beaten to death. I have been programming for eight years (not that long, but I'm not in my 20s yet and I got a programming job straight out of high school so I'm ...
5
votes
2answers
245 views

Reduce Prime Sieve Memory Consumption 2

I've made a prime number generator (for Project Euler). It uses Euler's Sieve (a modified Sieve of Eratosthenes), with a mod 30 step. I'd like to reduce the memory consumption to 4/15 what it ...
5
votes
3answers
26k 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 ...
5
votes
1answer
62 views

Prime Sieve and brute force #2

Based on my previous attempt. Prime Sieve and brute force Trying to make the interface simpler I have moved all the code into a class. This way I can keep track of the ...