We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [primes]

Primes or prime numbers are numbers which are divisible only by themselves and one, starting with 2, 3, 5, 7, 11.... They are commonly used in encryption and hashing algorithms.

Filter by
Sorted by
Tagged with
3
votes
3answers
521 views

Listing a number's prime factors

I wrote a little code to list a number's prime factors: ...
3
votes
3answers
1k 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 ...
12
votes
1answer
318 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: ...
8
votes
1answer
234 views
7
votes
1answer
1k views

Listing the first five perfect numbers in MIPS assembly

I've done some programming in the past, but I'm new to MIPS, which I'm trying to learn on my own. This program lists the first five perfect numbers. It uses the Lucas-Lehmer and Miller-Rabin primality ...
3
votes
1answer
469 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 ...
4
votes
2answers
332 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
25k 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 ...
8
votes
4answers
12k 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 ...
6
votes
2answers
1k views

Fermat primality test

Here is a simple working Java implementation of primality test for Fermat numbers. Is there something that I could change in code to achieve a better running time? ...
6
votes
3answers
1k 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
3k 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 ...
2
votes
6answers
3k views

Finding “lucky numbers”

This code is for a problem in which I'm to find the total number of numbers that exist between A and B, of which sum of digits and sum of square of digits are prime. How can I make this optimal? <...
18
votes
6answers
2k views

Is this C++ naive primality test done right?

Here's my C++ code: ...
4
votes
3answers
499 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 : ...
6
votes
2answers
576 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, <...
7
votes
7answers
4k 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 I ...
12
votes
7answers
9k 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 ...
10
votes
5answers
1k 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. ...
5
votes
2answers
690 views

Prime Number calculation bottleneck

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. ...
8
votes
6answers
4k 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. I'm using the following function to check if each number is prime: ...
3
votes
2answers
299 views

Python prime number generator

I'm trying to get a better grasp on generators in Python because I don't use them enough (I think generators are cool). To do so I wrote a generator for prime numbers: ...
3
votes
4answers
2k 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 ...
6
votes
4answers
3k views

Generating prime numbers within a range in C++

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
5k 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 ...
1
vote
1answer
2k views

Lazy computation of primes in Haskell

I wanted to give Haskell a try, and I started with a simple exercise I found here. Write isPrime :: Integer -> Bool, which determines whether a given ...
8
votes
4answers
762 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 ...
3
votes
7answers
7k 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 (integral ...
4
votes
2answers
707 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 ...
2
votes
1answer
832 views

Prime factorization of numbers up to 1000

I was reading Mathematics: A Very Short Introduction and it mentioned prime factorization. Being a curious person I had to write my own implementation in Perl. This program outputs the prime ...
4
votes
1answer
2k views

A random relative prime number based on the modulus

I am implementing RSA in java using BigInteger and I have a method to return a random relative prime number based on the modulus m. The method looks like this: ...
8
votes
3answers
2k 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 ...
1
vote
3answers
2k views

Filtered-Accumulate

Given the following task: Exercise 1.33 You can obtain an even more general version of accumulate (exercise 1.32) by introducing the notion of a filter on the terms to be combined. ...
38
votes
6answers
7k views

Calculation of prime numbers making use of Parallel.ForEach

In my spare time I decided to write a program that would systematically identify prime numbers from 2 to 18,446,744,073,709,551,615. This is for fun and learning, as I know it will take too long to ...
15
votes
2answers
2k 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 ...