# Tagged Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
929 views

...
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 ...
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 ...
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 ...
41 views

### Prime conjecture [closed]

I am trying to solve this SPOJ question. ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
934 views

### Is this C++ naive primality test done right?

Here's my C++ code: ...
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. ...
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. ...
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 ...
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 ...
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 ...