Tagged Questions

2answers
87 views

Finding prime numbers in a range

Finding the prime numbers between two given integers in the minimum number of comparisons: ...
4answers
380 views

...
3answers
119 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 ...
1answer
99 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: ...
2answers
137 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 ...
4answers
651 views

...
2answers
876 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 ...
1answer
197 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 ...
1answer
108 views

Strange performance difference

For exercise, I wrote this code: ...
3answers
701 views

Determining whether or not a number is prime

I wrote this code in Java without using any methods, just by using simple for loop and if statements. When we input a number, ...
0answers
116 views

Optimizing my Quadratic Sieve, with advice on style?

I'm still new to Haskell, and I'd like others' opinions on optimizing my basic quadratic sieve, in addition to feedback on the code's clarity and functional style. The ...
2answers
410 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 ...
2answers
271 views

Efficient way of code reuse for finding the largest prime factor

I was doing timing with variations of function largest_prime_factor. I was able to write a better one largest_prime_factor2. ...
1answer
168 views

Sphere Online Judge, Problem 2: Prime Number Generator

I am trying to solve this problem on Sphere Online Judge. I keep getting a timeout error. Any comments or suggestions are welcome and appreciated. ...
1answer
645 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 ...
1answer
128 views

Sierpinski gasket - patterns from primes

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 ...
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 ...
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. ...
3answers
144 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 ...
1answer
233 views

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: ...
1answer
178 views

...
2answers
285 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 ...
6answers
6k views

Yet another prime number generator

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 ...
4answers
384 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 ...
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 ...
2answers
418 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, ...
7answers
2k views

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 ...
5answers
4k views

Sieve of Eratosthenes

For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation. I would like to hear some suggestions for improvements, especially how to make it more efficient ...
2answers
435 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. ...
2answers
288 views

Optimizing this 'print up to the nth prime number' script

I've been seeking to optimize this algorithm, perhaps by eliminating one of the loops, or with a better test to check for prime numbers. I'm trying to calculate and display 100000 prime numbers has ...
3answers
1k views

Generating very large prime numbers and their generator modulo N in php

I recently came up with the idea to attempt generating ungodly large prime numbers and their generators modulo N in php. I don't know much about number theory and just wanted to get some comments to ...