Primes or prime numbers are numbers which are divisible only by themselves and one: 2, 3, 5, 7, 11, ...

learn more… | top users | synonyms (1)

2
votes
0answers
17 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 ...
8
votes
4answers
258 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. ...
4
votes
4answers
360 views
4
votes
4answers
351 views

Threshing: Sieve of Eratosthenes

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly. I made this super simple, trying to learn a little bit about ...
3
votes
2answers
623 views

Faster way to get all primes between 0 - n

Is there a faster way to get all primes between 0 - n ...
2
votes
1answer
36 views

Custom module of common functions

I got sick and tired of writing certain functions over and over again, so I made a module that has those functions whenever I need them. I don't use it for code I plan on sharing, so I don't need to ...
9
votes
4answers
2k views

Is prime check in Python: can this be more pythonic?

I have the following function that checks if a number is prime: ...
7
votes
2answers
89 views

Largest Prime Factor redux

There have been a number of questions asking for comments on code for the Project Euler problem to compute the largest prime factor of a number. A primary intent of this task is to find the factor as ...
4
votes
2answers
184 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 ...
10
votes
1answer
294 views

x64 Assembly - checking for largest prime factor

Using x64 assembly, I solved the Largest Prime Factor problem on Project Euler. The problem is as follows: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of ...
6
votes
4answers
289 views

A Fast Approach to Prime Number Sieving (Non-Threaded Array)

I am posting this question for input on comparisons between other sieving methods and opinions on what I have discovered. I believe this might be the fastest (singular, non-threaded) array ...
8
votes
5answers
478 views

Prime Number Sieving Algorithm

Edit: Newly Updated Code here A Fast Approach to Prime Sieving (Array Implementation - Non-Threaded) Original Thread Last semester in my Masters Program I developed this code for sieving. Is this ...
5
votes
3answers
80 views

Calculating the ranks of classmates' exam grades

The questions from hackerearth: Geeko is in worry now because an exam is coming up and he has to know what rank he can get on exams. So he goes back into the the school records and finds the ...
10
votes
1answer
94 views

Sieve of Atkins algorithm

I got the inspiration to write this algorithm from this question. The OP cited the Sieve of Atkin as one of the fastest ways to generate primes. So I figured I would give it a try: ...
4
votes
1answer
65 views

Checking for Prime Numbers [closed]

def is_prime(n): if n % 2 == 0 and n > 2: return False return all(n % i for i in xrange(3, int(math.sqrt(n)) + 1, 2)) The code works fine for a ...
6
votes
2answers
124 views

Prime Number Speed

I know prime number programs have been beaten to death. I am 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 ...
1
vote
4answers
636 views
5
votes
3answers
194 views

Psycho and ordinary numbers

The problem statement can be found here. In short, here's what the problem is about: You're given a set of numbers and you need to find whether the the numbers are ordinary or psycho. For a number ...
5
votes
1answer
361 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. ...
4
votes
2answers
63 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 ...
3
votes
2answers
161 views

Reduce Prime Sieve Memory Consumption

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 ...
6
votes
1answer
82 views

Make Project Euler 27 solution idiomatic Ruby

I learned to program in Java and C# and in my free time I am using Ruby because it is fun. Unfortunately I have the feeling that I write Ruby code like I am making Java or C# code. I have learned to ...
7
votes
3answers
168 views

Parallel sieve of Eratosthenes, version 2

This question is a revision of Parallel sieve of Eratosthenes. The goal is to implement a sieve of Eratosthenes with parallel strikes out from the boolean array. I tried to fix the data races and all ...
2
votes
1answer
64 views

Project Euler 27 - Quadratic Primes

Project Euler problem 27 I decided to try simple brute force, and it worked surprisingly quickly. How can this be optimized? ...
20
votes
5answers
1k views

Parallel sieve of Eratosthenes

For the first time, I tried to use threads by myself in order to implement a parallel sieve of Eratosthenes. The trick is that each time a prime is found, a thread is spawned to eliminate all the ...
8
votes
8answers
924 views

Project Euler #3 - largest prime factor

I was going through the Project Euler problem #3 and made a program to solve it. The problem is as follows: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of ...
10
votes
3answers
851 views
13
votes
4answers
1k views

Prime Number Generator - Are the conventions proper?

I am slowly learning C and C++, and decided after a few lessons to dive in myself without any help. I developed this Prime Number generator. It seems fast, but I'm wondering if I'm following the best ...
3
votes
2answers
200 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 <= ...
10
votes
4answers
741 views

Sieve of Eratosthenes in C++

I'm looking for some feedback on my implementation of the algorithm. How can I improve it? I ran into problems when calculating the larger prime numbers > 46349 due to integer overflow, but fixed that ...
17
votes
5answers
854 views

Count distinct primes, discarding palindromes, in under 2 seconds

Problem Statement Generate as many distinct primes P such that reverse (P) is also prime and is not equal to P. Output: Print per line one integer( ≤ 1015 ). Don't print more than ...
11
votes
2answers
830 views

First prime number larger than given integer

How can I test this C program for "efficiency"? The most interesting usage is that it returns negative output for large enough input, otherwise the behavior is about expected. Will you suggest how to ...
7
votes
2answers
228 views

Prime generator from one to n

My code calculates primes from one to n. I have verified that the code always produces all the primes in that range correctly. Are there any optimizations that I can make? Are there any bad ...
10
votes
2answers
380 views

First attempt at generating prime numbers

I had to look up some other solutions online because I could not figure it out on my own, which kinda sucks. I really wish I came up with it completely on my own but that didn't happen. Nevertheless, ...
7
votes
5answers
486 views

Ten thousand and first prime checker takes a very long time

I am attempting problem 7 on Project Euler. I have come up with this solution which works fine for finding smaller nth prime numbers, but really lags when it comes to higher nth prime numbers. I am ...
4
votes
3answers
113 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 ...
5
votes
6answers
310 views

Speeding up my implementation of Project Euler #3

Project Euler problem 3 asks for the largest prime factor of 600851475143. I have gone from 96 lines to 17 lines taking hits at this one. This is what I am left with after all of that effort: ...
13
votes
10answers
1k views

Prime number generator exercise

I have been trying to create a class that would list prime numbers forever. I know it has already been done but I think I learned some valuable principles during my trials. This project helped me ...
0
votes
2answers
40 views

Prime conjecture [closed]

I am trying to solve this SPOJ question. ...
3
votes
2answers
323 views

BigInteger prime testing

...
3
votes
1answer
175 views

Sum of two squares

I'm trying to do a SPOJ problem called twosquares where you check whether the current number can be obtained by adding two squares together. However, I'm getting a "time limit exceeded" message. I'm ...
11
votes
1answer
150 views

Tonelli-Shanks algorithm implementation of prime modular square root

I did an implementation of the Tonelli-Shanks algorithm as defined on Wikipedia. I put it here for review and sharing purpose. Legendre Symbol implementation: ...
4
votes
3answers
240 views

Prints out all ways to multiply smaller integers that equal the original number

Write a program in Java that takes a positive integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if ...
11
votes
4answers
276 views

Factorizing integers

I'm working on this method in Java, which is giving me the factors of a number. I'll be using this method a lot, and I was wondering if there isn't a better way of doing it. Like, with just one loop. ...
10
votes
2answers
165 views

Thread-safe prime number source

I am working on some multi-threaded code that requires a prime-number source. The following code keeps an array of primes in memory, extending it as needed. It works in the 'int' domain, being ...
10
votes
3answers
214 views

Project Euler “Largest prime factor” (#3) in Java

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I wrote the following code with help of some Java 8, I'll explain the equivalent ...
5
votes
4answers
845 views

Sieve of Eratosthenes - Python

I've been doing a lot of Project Euler lately and just wanted to make sure my implementation was as good as it could be. Does anyone have any suggestions on speed this up? ...
7
votes
1answer
107 views

Strange performance difference

For exercise, I wrote this code: ...
10
votes
4answers
281 views

Sieve of Eratosthenes optimization

I am making a program to find primes between the given range of numbers. Unfortunately, the algorithm I created is too slow. Do you have any ideas of how to optimize the code? ...
4
votes
1answer
148 views

Why does this python code take so long?

I don't understand what is taking the program so long: ...