Primes or prime numbers are numbers which are divisible only by themselves and one: 2, 3, 5, 7, 11, ... They are commonly used in encryption and hashing algorithms

learn more… | top users | synonyms (1)

5
votes
1answer
49 views

Isprime Android app with kivy

I thought that developing an app in Python should be easier than learning Java. I finally got my isprime app to work but it looks ugly. When I write GUI code I always find myself typing in very long ...
6
votes
2answers
147 views

Printing twin primes less than a given natural number n

I have two programs doing this task correctly, but at first I'm not sure if the code is correct (I mean absence of not efficient and superfluous pieces of the code). Then, I can't choose which one is ...
7
votes
4answers
123 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. ...
1
vote
0answers
18 views

Sum of N primes in parallel-ish

I'm primarily a C# guy--day job, most of my hobby projects, etc. Linq's AsParallel() call would be my normal way of doing something like this, but--tragically!--Rust hasn't stolen that just yet... ...
3
votes
0answers
88 views

Prime number generator

I have a small program that prints a sequence of prime numbers. I have tried to contact the author of this code, Erwin Unruh, but I didn't get a chance, regarding a couple of questions in meta ...
4
votes
1answer
88 views

Sieve prime generator C++

I had some issues with the behavior of the iterator in my prime generator: ...
3
votes
5answers
508 views

Find smallest prime number greater than given n

I need to write a program which will find a prime number, greater than the given n. Can it be done simpler? ...
5
votes
4answers
433 views

Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and R

A friend of mine recently started learning R, and she complained to me that R is very slow. She was working on Project Euler Problem 7, which asks for the value of the 10001st prime number. For ...
4
votes
1answer
54 views

Determine all prime, palindrome string integers within a range

I have written a program in Python 3x to determine all the prime, palindrome string integers in the range of two given numbers. ...
4
votes
2answers
101 views

Twin Prime Algorithm Optimization

I have wrote the following algorithm to print out the Nth twin prime numbers: ...
7
votes
2answers
341 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 ...
2
votes
2answers
78 views

C++ Prime Factorization

I just picked up C++ today and I wonder if this is c++-like. I have a bit of experience with Java. This is a program that takes a number as input and outputs its prime factorization in no particular ...
3
votes
3answers
791 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 ...
3
votes
2answers
115 views

Evaluating f(N,R) mod(m)

The goal is to find \$f(n,r)\mod(m)\$ for the given values of \$n\$, \$r\$, \$m\$, where \$m\$ is a prime number. $$f(n,r) = \dfrac{F(n)}{F(n-r) \cdot F(r)}$$ where $$F(n) = 1^1 \cdot 2^2 \cdot ...
4
votes
3answers
107 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: ...
-1
votes
1answer
78 views

Decomposing a number into primes

I have written the following code to decompose a number into primes. The problem is that it takes so much time and I have no idea why. ...
-1
votes
0answers
57 views

{STB} Spot the Bug: simple segmented Sieve of Eratosthenes for sieving up to 2^64-1 [closed]

To make a point in another topic, here's one take of the 'simplest possible sieve' that can sieve up to 2^64; the idea being to make things so brutally simple that we can trust the thing to be right ...
2
votes
1answer
46 views

Is there an easier way to find the prime factors of a number?

I am trying to write a program which, given a number as an input, prints the prime factors AND the exponents of the prime factors of that number. Example: ...
2
votes
2answers
110 views

Project Euler #3 - checking only up to sqrt(input)

I know it's possible for the largest factor of a number to be greater than the sqrt (e.g., for 14, 7 is the largest). Why then does almost every solution for the problem check only up to the square ...
5
votes
2answers
107 views

Quadratic Primes - Project Euler 27

Project Euler Problem 27 Euler discovered the remarkable quadratic formula: \$n^2 + n + 41\$ It turns out that the formula will produce \$40\$ primes for the consecutive values \$n = ...
1
vote
1answer
52 views

Writing a Pythonic prime sieve

I'm practicing writing code less by brute force. I'd like feedback for writing a prime sieve more Pythonic, simpler, or more creatively perhaps. ...
9
votes
6answers
733 views

Find primes using “naive” algorithm

I know I can use Sieves to make this faster, but I wondered if there's anything I'm missing with this implementation of the "naive" algorithm. On my PC running the command (first million primes): ...
10
votes
8answers
2k views

Find the nth prime between 1 and 1,000,000 in under 3 minutes - follow-up

Previous question: Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes My mission is to find the nth prime number, based on user input 1-1,000,000. ...
6
votes
4answers
141 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, ...
8
votes
7answers
2k views

Checking for the nth prime number between 1 and 1,000,000, must compute 1,000,000th in under 3 minutes

My mission is as the title states. Here is the original code, before optimizing slightly (but still not enough). Revised code is in my answer, and it still needs work. Also, I want to write this ...
8
votes
4answers
2k views

Printing 100 prime numbers

This is a program I wrote to print out 100 prime numbers. How can I improve it? ...
4
votes
5answers
364 views

Optimizing simple prime number function test

For my first basic project with functions, I wanted to make a program that would allow you to input a number, and it would output whether it was prime or not. For the most part, it's functional and ...
3
votes
3answers
145 views

Miller-Rabin Recursive Primality Test

I'm working on a primality test and have written a recursive function that returns the value of the function \$b^{q-1} \bmod q\$ where \$3<= q <= 32000\$ Is there any way to speed up ...
0
votes
1answer
69 views

Speeding up Mersenne prime generator

I am writing a program to calculate Mersenne primes. This code works, but it is so slow: ...
7
votes
7answers
2k 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
2answers
475 views

Sieve of Eratosthenes implementation is running slowly

I have written this code to find prime numbers, and it works well, but the calculation speeds are incredibly slow. Am I doing this wrong? I know that I might be really doing this the wrong way, but ...
10
votes
4answers
640 views

Prime Factorization

I'm doing an Objective-C project and I need to do some prime factorization and so I came up with the following algorithm which is 99% C, except for the array part which was easiest to implement in ...
4
votes
1answer
126 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? ...
4
votes
1answer
84 views

Channels vs. “for loop” prime number generator

I've found a question on SO (here), which is a prime number generator that uses channels. First of all, I had some trouble to find out how this code works, but later on, I saw the fun of it. Then, all ...
7
votes
2answers
216 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 ...
8
votes
5answers
560 views

Program for finding Fibonacci primes

I think it could have been designed with more object orientation. I don't like how one of my methods calls another from within the method, but I wasn't sure how to return the result because it is a ...
4
votes
4answers
548 views

Finding Primes in Java

I have a prime-finding class here that needs improvement. Sample result: ...
3
votes
2answers
99 views

List primes within an interval

I'm trying to solve the SPOJ primes problem: Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers! ...
1
vote
1answer
54 views

Speeding up prime factorization

I have written the following code for returning the list of prime factors. Any speed-enhancing suggestions? ...
10
votes
3answers
1k views

Wow that's a big integer! What's its largest prime factor?

I see that there are a few other people who have tackled Project Euler Problem #3. I hope you're not all sick of that question yet. I've not taken a look at those yet (purposely), but am about to now. ...
12
votes
4answers
611 views

Unit Testing for isPrime function

I've decided that I want to take a stab at test first programming. So, before I tackled writing an isPrime function, I wrote this unit test. It's my first and I'm ...
4
votes
1answer
130 views

Computation for finding the largest prime factor of 600851475143 is slow

I implemented the following for Project 3 in Project Euler: ...
5
votes
2answers
271 views

Finding prime numbers in a range

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

Replacing an F# loop over a mutable variable by an immutable approach

Consider: let mutable m' = m while m' % i = 0L do m' <- m' / i I've refactored it into: ...
12
votes
3answers
729 views

Finding largest prime factor from inputted number

This is my first C# console application. This program asks for an input of a number, and finds the highest prime factor of that number. Please review my code. Have I used things right? Is my code ...
4
votes
1answer
180 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
3answers
170 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 ...
13
votes
2answers
365 views

Generating prime numbers using Sieve of Eratosthenes with CUDA

I'm learning CUDA and wrote a little program which generates prime numbers using the Sieve of Eratosthenes. (I know the limitations of CUDA, specially with memory sizes and limits, but this program is ...
11
votes
4answers
311 views

Threshed and Malachi'd: Sieve of Eratosthenes

I took a little bit from all the answers to my previous question Threshing: Sieve of Eratosthenes. This may be bordering on code-golfing, but I think that I have a pretty good piece of code here. ...
5
votes
4answers
462 views