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)

7
votes
3answers
454 views

Checking if a number is prime

Is there a better way to check if a number is a prime? ...
3
votes
3answers
109 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
35 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
299 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
72 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
63 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
67 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
109 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
53 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
112 views
2
votes
2answers
65 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
40 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
50 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
227 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
136 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
80 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
115 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 ...
10
votes
3answers
771 views

Sum of First N Primes

Task: Print sum of first 1000 primes. ...
2
votes
2answers
923 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
578 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
133 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
104 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
57 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
129 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
80 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
38 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
131 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
108 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
61 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
98 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
379 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
151 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
31 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
113 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
102 views

Sieve prime generator C++

I had some issues with the behavior of the iterator in my prime generator: ...
3
votes
5answers
706 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
117 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
241 views

Twin Prime Algorithm Optimization

I have wrote the following algorithm to print out the Nth twin prime numbers: ...
7
votes
2answers
357 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
91 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
73 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
913 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
120 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
131 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
84 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
102 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
147 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 ...