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
7
votes
1answer
186 views

Hackerrank: Computer Game (max-flow problem with integer factorization)

I am working on a coding challenge from the Hackerrank site. Given two equal-length arrays of integers, with values from 2 to 109, find the maximum number of times we can remove a pair (Ai, Bj) where ...
7
votes
1answer
4k views

Number of prime numbers between 1 and n

I came up with the following solution to find the number of prime numbers from 1 to n. I'm wondering if there is a more optimal way. ...
7
votes
2answers
581 views

Project Euler 357 prime number generator in Python 3

I'm brute forcing the Project Euler 357 since no better algorithm comes to my mind. The challenge asks: Find the sum of all positive integers n not exceeding 108 such that for every divisor d of n, ...
7
votes
1answer
429 views

The rusty Sieve of Eratosthenes

To get familiar with the Rust language I've decided to implement the method of Sieve of Eratosthenes to find primes up to a number N. I have created the following code that both prints the prime ...
7
votes
1answer
549 views

Maximum performance for Pollard's P-1 function

I am trying to find mersenne primes using python, and following the advice from https://www.mersenne.org/various/math.php, I have an intermediate step where I am using Pollard's P-1 factoring ...
7
votes
1answer
6k 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 ...
7
votes
4answers
946 views

Python Prime Testing

This code seems surprisingly fast at checking if a number is prime. ...
6
votes
6answers
378 views

Speeding up my implementation of Project Euler #3

Project Euler problem 3 asks for the largest prime factor of 600851475143. I have gone from 96 lines to 17 lines taking hits at this one. This is what I am left with after all of that effort: ...
6
votes
4answers
1k views

Threshing: Sieve of Eratosthenes

I would like a complete threshing of this code so that I can see what I did wrong and what I am using incorrectly. I made this super simple, trying to learn a little bit about ...
6
votes
2answers
11k views

What is the 10001st prime number?

Project Euler problem 7 says: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number? I believe that my code is ...
6
votes
6answers
3k views

Largest prime factor for a given number

I created a program to find the largest prime factor for a given number. The program works but unfortunately takes very long time to compute a huge number like 600851475143. How can I optimise this ...
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 ...
6
votes
3answers
919 views

Sieve Of Erastothenes using Java

have started learning Java recently and was looking into some easy algorithms. I found the Sieve Of Erastothenes algorithm here I am trying to get better at writing good code for my solutions. Please ...
6
votes
2answers
1k 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 ...
6
votes
1answer
80 views

Generating prime candidates

I'd like to generate an infinite list of prime candidates of the form 6k±1, but I'm looking for the fastest possible solution. Currently I have this: ...
6
votes
2answers
37k views

Printing the n'th prime numbers

This is an online problem. The challenge is to print the kth prime number, for each k given in the input (1 ≤ k ≤ 15000). The first line of input indicates the number of inputs on the subsequent N ...
6
votes
4answers
2k views

Project Euler 50 in Python

Project Euler, problem #50: The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime ...
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 ...
6
votes
1answer
226 views

Counting primes in a range whose digits are all prime

Codewars Kata: Given integers a and b, count all primes p where a ≤ p < b and the digits of p are all prime. b may be as large as 107. To start with, I hardcoded all valid 1903 primes in \$[1, 10^...
6
votes
2answers
212 views

Divisor game cheating aid

This code outputs the smallest number with more divisors than the input: ...
6
votes
2answers
308 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 = 0\$...
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
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, <...
6
votes
4answers
106 views

Calculate the number of primes in a range

I wrote some code to return how many prime numbers are in a specific range and what they are. It also tells you whether the number of primes is also a prime! I feel like this seems like a fairly long ...
6
votes
2answers
137 views

Find prime factors and reverse strings

I'm currently taking an introductory course to Bash at my university, and was hoping to get some peer-review from whoever might have some time. Full disclosure: the quality of the code isn't ...
6
votes
3answers
432 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 ...
6
votes
2answers
249 views

Returning the prime factors of a number

I am trying to create a function prime-factors that returns the prime factors of a number. To do so, I created is-prime function,...
6
votes
2answers
102 views

Simple prime factorization program in Haskell

I'm finally learning Haskell this summer and I have a few questions about conventions. I made a simple prime factorization program which is surprisingly fast, much faster than the ones I made in C++ (...
6
votes
2answers
4k 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 ...
6
votes
1answer
135 views

Check sum of all primes under two million

I'm exploring ruby by writing a code that checks the sum of all prime numbers under two million. As I am still in the process of learning ruby, I'm unfamiliar with all the standards and best practices....
6
votes
1answer
6k views

Calculating prime factors in MIPS assembly

The goal of this was to be able to enter any number and print out the prime factors of that number. Are there any shorter ways of writing this code? I'm not very familiar with low-level syntax and was ...
6
votes
5answers
605 views

Python prime number checker function

I was bored, and I was watching a sci-fi show where people were starting out during a long systems check asking each other whether numbers were prime or not, sort of passing the time as they do their ...
6
votes
1answer
592 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 ...
6
votes
2answers
193 views

A simple implementation of the principle of RSA encryption

Inspired by a Numberphile video I made a little program that shows the principles of RSA encryption and decryption. To calculate the keys I used the explanation in this link: rsa public private key ...
6
votes
1answer
170 views

Generating smooth numbers in Haskell

I wrote a smooth function that returns a list of all smooth numbers below a certain limit from a list of prime: ...
6
votes
1answer
151 views

C the sum of primes

The challenge is to calculate the sum of the first 1000 primes. The code applies a sieve thanks to past answer, here, and works but I wonder about the flexibility of this solution. ...
6
votes
1answer
108 views

Returns all primes p between m <= p <= n

This is my submission for the Prime Generator on SPOJ and it was accepted. Are there any improvements/changes I can make? Input: The input begins with the number \$t\$ of test cases in 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
2answers
613 views

General primality test in C++

I have this code, which I think can be optimized even more, but I can't think of a way of optimizing the main loop to make it faster and more comprehesive. Here's the code: ...
6
votes
2answers
893 views

Prime multiplication table

I am new to Ruby (1 year as hobby project on weekends) and solved a code challenge and it was not as good as they wanted. I want to know how i could make it better and how to make the structure better....
6
votes
1answer
295 views

Sieve of Eratosthenes for prime generation

I was originally going to write this intro as just being the bare-bones "here's my problem, here are some ideas, what do you recommend" format (which I am still going to follow, mind you), but I've ...
6
votes
1answer
2k views

Generating and using a list of prime numbers

Here is some code I've created to generate and use a list of prime numbers. This is some of the first Common Lisp code I've written, and I'd be grateful for any comments regarding style and its use ...
6
votes
1answer
114 views

Decompose any number to its prime factors raised to their respective powers

A simple code which takes the given number as input and gives all of its prime factors raised to their respective powers...works well upto 106 after that it slows down greatly for some numbers..but ...
6
votes
1answer
143 views

Lucas Lehmer Primality Test

I have coded the Lucas-Lehmer primality test following Wikipedia's description. I used the mod 2^n - 1 suggested in the article but was wondering if there were any ...
6
votes
3answers
2k views

Prime factorization in Haskell

I am a Haskell beginner. Here is my function to find prime factors of a number ...
6
votes
1answer
488 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 ...
6
votes
1answer
119 views

Fast prime generator

I wanted to test my performance optimizing skills, and so wanted to find how fast I could get the first \$n\$ prime numbers. I limited myself to only the standard library, as I'm sure ...
6
votes
1answer
126 views

Python3 - Prime Sieve

I've implemented two prime sieves in python 3 to find all prime numbers up to an upper limit n - n exlusive. The first one is ...
6
votes
1answer
2k views

Down to Zero II

Problem : https://www.hackerrank.com/challenges/down-to-zero-ii You are given queries. Each query consists of a single number N. You can perform 2 operations on N in each move. If N=a*b (a!=1,b!=...
6
votes
1answer
124 views

Prime numbers using wheel factorial

I have written a program to find prime numbers up to a given limit using wheel factorization of 2, 3 and 5. I would like it to work above \$10^{10}\$, but its still pretty slow. What else can I ...