Primes or prime numbers are numbers which are divisible only by themselves and one: 2, 3, 5, 7, 11, ...
3
votes
1answer
79 views
Prime Numbers Store
Problem definition:
Lets say we need to create a store for selling prime numbers.
Users enter the store and ask to buy a number.
If the number asked is a prime number,
1.1. then it's either ...
2
votes
1answer
89 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 should I make to pass it.
...
3
votes
1answer
89 views
Project Euler 407: Is there any more optimal way to solve this idempotent equation (modulo n ring)?
Project Euler problem 407:
If we calculate a2 mod 6 for 0 ≤ a ≤ 5 we get: 0, 1, 4, 3, 4, 1.
The largest value of a such that a2 mod 6 = a is 4.
Let's call M(n) the largest value of a < n ...
-1
votes
0answers
43 views
CodeReview:Miller Rabin Primality Test algorithm implementation in C and python [closed]
I have written a python code implementing Miller Rabin Primality Test
The code finds the largest prime less than the input. Here is a code snippet of primality testing algorithm
def ...
1
vote
3answers
90 views
Project Euler problem 37: truncatable primes
I am working on Project Euler problem 37 and I have the following program:
#!/usr/bin/ruby -w
require 'prime'
h=11
y=0
x=0
while x < 11
if h.prime? == true
boo = true
f=0
...
2
votes
1answer
86 views
Help me speed up this Java code. Deals with HUGE list of ints
Below is the code I have written. I started yesterday with prime numbers and playing around with them. What the code does it determines the "prime gap" between primes numbers, prints them, then finds ...
3
votes
1answer
64 views
Quadratic Primes
This is one of the slightly trickier Project Euler Questions I have seen (Question 27)
Considering quadratics of the form:
n² + an + b, where |a| < 1000 and |b| < 1000
where |n| is the ...
4
votes
4answers
203 views
Sum of primes less than 2,000,000
I have been attempting the questions at Project Euler and I am trying to find the sum of Primes under two million (question 10)
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the ...
4
votes
2answers
102 views
Prime sieve: improve efficiency while keeping it reasonably simple?
public static void listPrimesThree(int maxNum){
long startTime = System.currentTimeMillis();
boolean[] booleanArray = new boolean[maxNum+1];
int root = (int)Math.sqrt(maxNum);
for (int m = 2; m ...
1
vote
1answer
83 views
Optimizing code for project-euler p#23
I'm working on project euler's problem #23, wich is
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers
So I came up with this algorithm. Find ...
5
votes
1answer
178 views
Is this the most efficient way to see if the number is prime?
my question is in the title really...is this the most efficiant way to find if a number is prime?
public boolean primes(int num){
for(int i = 2; i < num; i++){
if(num % i == 0){
...
0
votes
2answers
105 views
C++: 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 online judge is still complaining that time limit is exceeding. Maybe I'm ...
0
votes
1answer
77 views
Miller-Rabin Prime test (Speed is the main goal)
The code below is for testing Primes.
testPrime(100000);
testPrime(1000000);
testPrime(10000000);
testPrime(100000000);
Now my goal is to make the code super fast at finding prime number, min-max, ...
0
votes
1answer
61 views
Project Euler 10: Summation of primes in Go
Here is my first try at googles Go language, trying to solve Eulers Problem 10:
http://projecteuler.net/problem=10
Any suggestions on the style and usage (best practice) of Go?
One more thing, ...
-1
votes
1answer
94 views
How to apply Sieve of Eratosthenes test into my code [closed]
I have this code that tests prime numbers and I'm trying to make it fast as possible. I know a way but I just can't find how to execute it in to my code. Does any one know how to input in to the code ...
2
votes
1answer
96 views
Simple and efficient code for finding factors and prime factorization?
I've modified this program many times, but I want to know if this is a good way to perform this task. My first algorithm for finding the factors of a number was pretty slow and horrible (started at ...
0
votes
0answers
61 views
Bit array not working as fast as expected [closed]
I recently downloaded the bitarray module from here, for a faster prime sieve, but the results are dismal.
from bitarray import bitarray
from numpy import ones
from timeit import timeit
def ...
0
votes
3answers
175 views
Primes Tester for speed performance
I was given a homework assignment in Java to create classes that find Prime number and etc (you will see in code better).
My code:
class Primes {
public static boolean IsPrime(long num) {
...
7
votes
1answer
216 views
Project Euler #3 - how inefficient is my code?
So I am essentially a complete newbie to programming, and have been attempting to learn Python by completing the Project Euler problems. I haven't gotten very far, and this is my code for problem #3 :
...
2
votes
2answers
142 views
Criticize my first Python module please
This is a Python module I have just finished writing which I plan to use at project Euler. Please let me know how I have done and what I could do to improve it.
# This constant is more or less an ...
2
votes
1answer
73 views
Largest Prime Factor
I'm trying to learn Python by working my way through problems on the Project Euler website. I managed to solve problem #3, which is
What is the largest prime factor of the number 600851475143 ?
...
4
votes
2answers
215 views
Any better way to solve Project Euler problem # 5
So, here's my attempt on Problem # 5 of Project Euler, which is looking quite clumpsy when seen first time. Is there any better way to solve this? Or any built-in library that already does some part ...
2
votes
1answer
87 views
Code review needed for my Prime factorization code
Below is the code for knowing all the prime factors of a number. I think there must be some better way of doing the same thing. Also, please tell me if there are some flaws in my code.
def ...
3
votes
2answers
76 views
Get a limit number to test all the prime numbers it contains in C
My task was:
Write a program that accepts an integer as input and then displays all the prime
numbers smaller than or equal to that number.
And my code is:
#include <stdio.h>
void ...
1
vote
2answers
92 views
SPOJ problem2 Prime Generator : How to make my code better and faster? (in C)
Trying to solve this problem. After couple of tries this is what i could pull off
#include<stdio.h>
#define primeLimit 100000
int prime (long int Start2, long int Stop2 )
...
1
vote
3answers
279 views
Need a faster way to determine prime numbers than my algorithm
The problem I am solving is: "What is the largest prime factor of the number 600851475143?" The first step I took is to determine the highest value number I should be looking at as a possibility ...
4
votes
5answers
249 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 ...
2
votes
2answers
111 views
Random Prime generator
I have this method that will give a random prime for a given range (min inclusive an max not inclusive) all comments are welcome:
public static int randomPrime(int min, int max) {
if (min < 0)
...
6
votes
1answer
95 views
Sundaram's sieve in Common Lisp
I have this Sundaram's sieve to generate prime numbers up to limit in Common Lisp.
(defun sundaram-sieve (limit)
(let ((numbers (range 3 (+ limit 1) 2))
(half (/ limit 2))
(start ...
3
votes
1answer
113 views
Functional Sundaram's sieve
I wrote this Sundaram's sieve in Coffeescript to quickly generate prime numbers up to limit:
sieve_sundaram = (limit) ->
numbers = (n for n in [3...limit+1] by 2)
half = limit / 2
...
0
votes
2answers
243 views
Functional prime factor generator
I have this prime factor generator for some number n. It returns list of all prime factors. In other words, product of the list equals n.
def prime_factors_generate(n):
a = []
prime_list = ...
3
votes
3answers
117 views
Naive prime finder, unexpected behavior in Python
I have verified that both of my following functions successfully find prime numbers. I was pretty sure the function called is_prime_new would be faster than is_prime_old; however, after benchmarking ...
3
votes
3answers
166 views
Prime numbers, Prime Factors and LCM
I am trying to generate LCM by prime factorization. I have already done the other way around to generate LCM using GCD but I am trying to achieve it using prime factorization.
I am getting right ...
2
votes
0answers
107 views
Improving the efficiency of a depth-first search method for searching for all “superpalindromes” whose prime factors are all <=N?
A question was asked over at math.SE (here) about whether or not there are infinitely many superpalindromes. I'm going to rephrase the definition to a more suitable one for coding purposes:
...
3
votes
1answer
139 views
Scheme, first timer first program, simple list removal technique
I have started my hand at writing some scheme code. I am trying to get the first n primes. I plan to do so but first getting a list from 2 to m, and doing the following algorithm. Remove the first ...
4
votes
2answers
232 views
Improving runtime of prime generation
I just answered the question on project euler about finding circular primes below 1 million using python. My solution is below. I was able to reduce the running time of the solution from 9 seconds to ...
5
votes
3answers
3k 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 ...
3
votes
4answers
1k views
Yet another prime number generator code review
The question asked to find all the prime numbers within a particular range. The way I approached this was to loop through each of the numbers within the range and for each number check whether it's a ...
3
votes
6answers
2k views
Find the largest Prime Factor of the number 600851475143
I am trying to complete this challenge, which is to find the Find the largest Prime Factor of the number 600851475143.
My current solution is below:
static void Main(string[] args)
{
const long ...
3
votes
2answers
203 views
Improvements for isPrime C++ function
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 ...
4
votes
6answers
724 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 ...
11
votes
6answers
609 views
Is this C++ naive primality test done right?
Here's my C++ code:
bool isPrime(double value) {
if (value == 2) // ensure 2 returns true
return true;
else if (value <= 1) // eliminate 1 and all ...
4
votes
4answers
152 views
Finding and testing primality
I have written a class who is responsible for both enumerating primes and testing the primality of a number.
Here is the code :
public static class Primes
{
private static ulong g_MaxTested;
...
4
votes
2answers
277 views
Euler 35 - python solution taking too long
Here is my solution for Project Euler 35. (Find the number of circular primes below 1,000,000. Circular meaning all rotations of the digits are prime, i.e. 197, 719, 971.) The code takes about 30 ...
5
votes
6answers
1k views
Puzzle: sum of the digits is prime or not
Puzzle Description: A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between A and B are lucky?
How can I improve ...
2
votes
2answers
288 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.
unsigned int ...
8
votes
6answers
2k 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
int ...
1
vote
5answers
856 views
Sieve of Eratosthenes: making it quicker
I was thinking about doing problem 23 of Project Euler. It includes the difficulty where you have to factorize primes. I had already done that in problems I solved earlier, but it was only necessary ...
5
votes
4answers
450 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 ...
4
votes
4answers
1k views
Prime number calculator
I am starting to learn Ruby.
This is pretty much the first thing I have coded. It's very simple; it's a prime number calculator. Since this is my first Ruby code, I would like some review on the ...
