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

learn more… | top users | synonyms (1)

3
votes
2answers
50 views

Sieve of Eratosthenes in C#

Just because I've never written a real Sieve of Eratosthenes, I decided I should probably write one just to make sure I know what it is. I'd like (constructive) criticism on best practices, potential ...
3
votes
1answer
29 views

Factors sieve optimization

I have written a more powerful version of the sieve of Eratosthenes: this sieve returns the number of factors of all the numbers below the limit. Sadly the running ...
6
votes
2answers
261 views

Sum the exponents of the prime factors of a number

My goal is to find the sum of the exponents of the prime factors of an integer. I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though): Runtime ...
4
votes
1answer
52 views

Prime number calculator using Sieve of Eratosthenes

I've been writing this prime number calculator, and I've gotten it pretty quick in comparison to most I've seen knocking about. This one uses the Sieve of Eratosthenes approach, and I've optimised the ...
4
votes
3answers
58 views

Prime factorization of an integer

I have just started learning functional programming (Haskell) for fun after using imperative languages my whole life. I am looking for quick and simple tips from pros on how the particular code I just ...
2
votes
2answers
59 views

Prime factors of a number in C

The following is code on "prime factors of a number". Any suggestions to optimize the code? It runs for a pretty long time for inputs like 35068499. I also want the code to take 10 digit numbers as ...
6
votes
3answers
96 views

Sieve of Sundaram for Project Euler 7

This is a sequel to my previous question: Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and R I am trying to implement the Sieve of Sundaram in various languages to ...
3
votes
2answers
49 views

Factorisation code running slow

I'm still in the process of learning Python and am doing some of the Project Euler problems. I have made a factorisation algorithm that works; however, it runs really slowly, and I'm not too ...
3
votes
3answers
107 views
2
votes
2answers
52 views

Sieve of Eratosthenes JavaScript implementation - performance very slow over a certain number

I've been playing around with the code challenges on projecteuler.net. A few of them involve prime numbers, so I've created a function to find them based on the sieve of Eratosthenes. It works fine, ...
1
vote
1answer
38 views

Naive primality test and summation

I am starting to learn Haskell, so I coded a naive solution to the primality test and summation of primes (Project Euler Problem 10: sum of all primes under 2 million) . As I have an imperative ...
1
vote
0answers
44 views

English phrases, prime numbers, pseudo random data and encryption source code check

This code uses a DCG and pairs phrases into near-English sentences. If anyone is familiar with Prolog, I'm wondering how I can use the code as an encryption method by hiding data and replacing it ...
5
votes
1answer
176 views

Listing the first 100 prime numbers

I thought of this implementation, and I want to get feedback from you.. what design would you use for printing first 100 prime numbers? I used the fact that, if the number is not divisible by any ...
3
votes
3answers
116 views

Project Euler 35: Circular primes below 1 million

I'm doing another Project Euler problem, number 35, and I need help improving my code speed: The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, ...
4
votes
7answers
2k views

Project Euler #10 — Summation of primes takes forever

I have resolved the Problem presented in Project Euler #10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. But this code takes too ...
6
votes
1answer
71 views

Making prime (sieve) code faster and able to run on big numbers

For an input triple (a, b, c), the task is to count the number of integers in the inclusive range [a, b] which have c distinct prime factors. This entails factoring each of the numbers in the range ...
5
votes
1answer
65 views

Printing prime numbers in Assembly

I am learning to code in the Assembly language for the x86 architecture. I currently know of a few registers and certain arithmetic operations like add, sub, inc, dec, mov and to check for ...
8
votes
3answers
750 views

Sum of First N Primes

Task: Print sum of first 1000 primes. ...
2
votes
2answers
573 views

Prime numbers less than a given number N

So, I began this challenge on CodeEval, which asks to print out the number of prime numbers less than any given integer N, where 0 < N < 4,294,967,295, ideally in O(N log N) time. I came up ...
5
votes
5answers
562 views

Improving isPrime method

I've been doing some programming challenges and problems lately and it seems like many involve primes. I concluded that I would benefit from optimizing how I'm checking for them. Currently I'm using ...
4
votes
3answers
125 views

Project Euler Problem #10

I've read other solutions about solving the 10th problem for Project Euler (finding the sum of all prime numbers under 2,000,000) but I wanted to try it on my own using the Sieve of Eratosthenes ...
1
vote
2answers
101 views

Haskell monads: sum of primes

They say you cannot get out of the monad, but I need to use the result (at least for assertions / unit tests). But print how does it do it? Otherwise, I worked ...
2
votes
1answer
51 views

Project Euler #12 in Swift - Highly divisible triangular number

I just finished Project Euler #12 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. The sequence of triangle ...
2
votes
1answer
80 views

A prime number sieve using recursion

Out of curiosity, I built a recursive Sieve of Eratosthenes in Python and I was wondering how it could be improved for efficiency and how it can improved to be aligned with python best practices. ...
5
votes
1answer
72 views

Project Euler #10 in Swift - Summation of primes

I just finished Project Euler #10 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. I hope I learned some from ...
1
vote
1answer
36 views

Project Euler #3 in Haskell

Project Euler #3 asks: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I've written a general solution for any number: ...
12
votes
6answers
1k views

Prime Number Checker

This is my prime number checker in C++. I know that calculating the square root of a number can be very costly, so I don't do it unless the number is larger than 10k, where we would have to check ...
6
votes
2answers
128 views

Project Euler #7 - 10001st prime

I just finished Project Euler #7 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it. By listing the first six ...
3
votes
2answers
98 views

Prime Number Sequence generator

I have just started using Python, and I am attempting to make a prime number sequence generator, where it will print the a specified amount prime numbers in terminal. I have other versions of this ...
1
vote
1answer
43 views

Prime Number Sieve Optimization

I've written my own prime number sieve in JavaScript. It loops through numbers 1-100 and puts them in one of two arrays, depending on if it is composite or prime. I was wondering if there are any ...
5
votes
1answer
84 views

Isprime Android app with kivy

I thought that developing an app in Python should be easier than learning Java. I finally got my isprime app to work but it looks ugly. When I write GUI code I always find myself typing in very long ...
6
votes
2answers
286 views

Printing twin primes less than a given natural number n

I have two programs doing this task correctly, but at first I'm not sure if the code is correct (I mean absence of not efficient and superfluous pieces of the code). Then, I can't choose which one is ...
7
votes
4answers
146 views

Test a number for primality and return smallest divisor different from 1 if it’s is composite

In this exercise we were asked to test a number for primality and print the results. Additionally – in the case the number is composite – the smallest divisor different from 1 should be printed out. ...
1
vote
0answers
30 views

Sum of N primes in parallel-ish

I'm primarily a C# guy--day job, most of my hobby projects, etc. Linq's AsParallel() call would be my normal way of doing something like this, but--tragically!--Rust hasn't stolen that just yet... ...
4
votes
0answers
106 views

Prime number generator

I have a small program that prints a sequence of prime numbers. I have tried to contact the author of this code, Erwin Unruh, but I didn't get a chance, regarding a couple of questions in meta ...
4
votes
1answer
99 views

Sieve prime generator C++

I had some issues with the behavior of the iterator in my prime generator: ...
3
votes
5answers
620 views

Find smallest prime number greater than given n

I need to write a program which will find a prime number, greater than the given n. Can it be done simpler? ...
8
votes
4answers
1k views

Sieve of Sundaram for Project Euler 7: Python implementation slower than C++ and R

A friend of mine recently started learning R, and she complained to me that R is very slow. She was working on Project Euler Problem 7, which asks for the value of the 10001st prime number. For ...
4
votes
1answer
71 views

Determine all prime, palindrome string integers within a range

I have written a program in Python 3x to determine all the prime, palindrome string integers in the range of two given numbers. ...
4
votes
2answers
200 views

Twin Prime Algorithm Optimization

I have wrote the following algorithm to print out the Nth twin prime numbers: ...
7
votes
2answers
350 views

Counting Fermat witnesses and liars

We were asked to implement a program that calculates the number of Fermat witnesses and liars for odd numbers greater 1. This involves Fermat’s little theorem. Fermat’s little is used to identify ...
2
votes
2answers
87 views

C++ Prime Factorization

I just picked up C++ today and I wonder if this is c++-like. I have a bit of experience with Java. This is a program that takes a number as input and outputs its prime factorization in no particular ...
3
votes
1answer
61 views

Time limit exceeded for SPOJ problem “Prime Generator”

Input The input begins with the number \$t\$ of test cases in a single line (\$t \le 10\$). In each of the next \$t\$ lines there are two numbers \$m\$ and \$n\$ (\$1 \le m \le n \le ...
3
votes
3answers
858 views

Calculate highest prime factor very slow

Sometimes when I write a Python 3.x script with too many nested loops and some big values it just takes too long to give the answer. How can I optimize my code so that it runs faster, or where should ...
3
votes
2answers
119 views

Evaluating f(N,R) mod(m)

The goal is to find \$f(n,r)\mod(m)\$ for the given values of \$n\$, \$r\$, \$m\$, where \$m\$ is a prime number. $$f(n,r) = \dfrac{F(n)}{F(n-r) \cdot F(r)}$$ where $$F(n) = 1^1 \cdot 2^2 \cdot ...
4
votes
3answers
124 views

Prime less than N that is a sum of the most consecutive other primes

Here's a Python implementation of the Sieve of Eratosthenes: ...
-1
votes
1answer
80 views

Decomposing a number into primes

I have written the following code to decompose a number into primes. The problem is that it takes so much time and I have no idea why. ...
2
votes
1answer
77 views

Is there an easier way to find the prime factors of a number?

I am trying to write a program which, given a number as an input, prints the prime factors AND the exponents of the prime factors of that number. Example: ...
2
votes
2answers
138 views

Project Euler #3 - checking only up to sqrt(input)

I know it's possible for the largest factor of a number to be greater than the sqrt (e.g., for 14, 7 is the largest). Why then does almost every solution for the problem check only up to the square ...
5
votes
2answers
119 views

Quadratic Primes - Project Euler 27

Project Euler Problem 27 Euler discovered the remarkable quadratic formula: \$n^2 + n + 41\$ It turns out that the formula will produce \$40\$ primes for the consecutive values \$n = ...