4
votes
3answers
145 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 ...
7
votes
2answers
103 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 ...
5
votes
3answers
228 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 ...
4
votes
2answers
67 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
165 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 ...
7
votes
3answers
179 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 ...
21
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 ...
10
votes
8answers
965 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
929 views
15
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 ...
11
votes
4answers
849 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 ...
7
votes
2answers
230 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 ...
0
votes
2answers
41 views

Prime conjecture [closed]

I am trying to solve this SPOJ question. ...
3
votes
4answers
543 views

Relative prime numbers

Two integers a and b are relatively prime if and only if there are no integers: x > 1, y > 0, z > 0 such that a = xy and b = xz. I wrote a program that determines how many positive integers less ...
2
votes
3answers
210 views

Project Euler #12 in C++ - highly divisible triangular number

Project Euler Problem 12 asks (paraphrased): The nth triangular number Tn = 1 + 2 + … + n. T7 = 28 has 6 divisors (1, 2, 4, 7, 14, 28). What is the first Tn to have over 500 divisors? After ...
7
votes
2answers
409 views

Improving remake of factoring/prime factorization calculator

Background info on factoring and prime factorization. I've remade this program from my first attempt, and I'm sure it can still be improved. My questions: These calculations should only be done ...
3
votes
2answers
240 views

Object-oriented design of list of primes

Is there a better way to implement this class, or does it not constitute implementation in the first place? This is one of my first few tries at OOP. Any suggestions will be much appreciated. ...
3
votes
2answers
98 views

First use of std::map in factors and prime factorization program

This is from an older question of mine that I decided to revisit: Simple and efficient code for finding factors and prime factorization? In that question, someone suggested I use an ...
7
votes
2answers
359 views

Greatest prime number smaller than N where N can be as large as 10^18

This is code for finding largest prime number smaller than \$N\$, where \$N\$ can be as large as \$10^{18}\$. But, it takes 1 minute for \$10^{18}\$. I need to pass it in 2-3 sec. What changes ...
0
votes
3answers
3k views

Prime Number Generator algorithm optimization

I've implemented a simple program that finds all prime numbers between two integer inputs using Sieve of Eratosthenes, but the online judge is still complaining that the time limit is exceeding. Maybe ...
4
votes
1answer
1k views

Simplifying and optimizing factors and prime factorization generator

My first algorithm for finding the factors of a number was pretty slow and horrible (it started at \$O(n^2)\$, where n was not even the inputted number), but I eventually came up with this new code. ...
5
votes
5answers
816 views

How to optimise a for loop in a factor search to run faster?

I created a program to find the largest prime factor for a given number. The program worked but unfortunately it takes very long time to compute a huge number like 600851475143. How can I optimise ...
5
votes
4answers
383 views

Generating primes with Sieve of Eratosthenes

There are many problems on the Internet that require you to find prime numbers, so I decided to write a set of functions to find them. I used the Sieve of Eratosthenes for generating the primes as it ...
6
votes
5answers
1k views

Optimization - Prime Factorizations of Numbers <= 10^7

I am using Trail Division Method with a pre-calculated list of primes to calculate the prime factorization of all numbers less than M (M <= 10^7). I am using an array of vectors of pairs. The ...
13
votes
6answers
934 views

Is this C++ naive primality test done right?

Here's my C++ code: ...
8
votes
5answers
912 views

Sieve of Eratosthenes in C++11

Please point out every problem you see with this code. Any fundamental flaws, naming conventions, design decisions, you name it. ...
3
votes
2answers
434 views

Prime Number calculation bottleneck help

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. ...
11
votes
6answers
3k views

Sum of all primes under 2 million

I have this assignment to write the optimized space and time code for finding the sum of all primes under 2 million in c/c++. Im using the following function to check if each number is prime ...
5
votes
4answers
802 views

Please comment on this code for generating prime numbers within a range

I was given a problem to find out all the prime numbers within a range. Just after I wrote the program I found numerous other codes to solve the problem. I am interested to know is my algorithm ...
10
votes
4answers
421 views

Prime generator

I'm coming from a Python background(look at indentation :) ) and trying to learn basics of C++. I wrote a simple prime generator, I know there is better algorithms, but I want advices about coding ...
2
votes
7answers
3k views

Prime number finder

There's another exercise from Thinking in C++. This time it asks this: Write a program that uses two nested for loops and the modulus operator (%) to detect and print prime numbers ...
7
votes
2answers
449 views

Eratosthenes sieve and MPI

I wrote this sieve of Eratosthenes with MPI, but I'm not sure if it's good enough. Should I use MPI_Scatter and MPI_Gather ...