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.

1
vote
0answers
34 views

Parallel Miller-Rabin Prime Test in Haskell

I implemented a prime number finder using the Miller-Rabin prime test in Haskell and it seems to be working. You enter a number and it finds the next prime following that number. I also tried to make ...
10
votes
3answers
2k views

Prime sieve in Python

I was trying to write Sieve for the first time and I came up with this code: ...
8
votes
2answers
752 views

Primes and SemiPrimes in Binary

I'm in the midst of re-learning python. My current effort is an implementation around prime factorization. I am attempting to reproduce something similar to the table found here (in binary): https://...
4
votes
4answers
147 views

Find the nth term of a sequence that consists of Fibonacci and prime numbers interleaved

I have given a series problem 1,2,1,3,2,5,3,7,5.... in which the odd terms forms the Fibonacci series and even terms form the prime number series. I have to write a code in which I have to find the ...
7
votes
2answers
885 views

Arranging numbers in a circle such that the sums of neighbors and sums of diametric opposites are prime

I need to create a circle with numbers from 1 to n , however it is necessary to respect some rules: All numbers from 1 to n are used in the circle only once. The sum of two consecutive numbers ...
5
votes
1answer
49 views

Prime Sieve and brute force #2

Based on my previous attempt. Prime Sieve and brute force Trying to make the interface simpler I have moved all the code into a class. This way I can keep track of the ...
14
votes
3answers
1k views

Prime Sieve and brute force

Got caught up with this morning's C++ question. So I thought I would have a go. SO here is my attempt at printing the first 1001 primes. ...
3
votes
0answers
54 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
2answers
53 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++ (...
4
votes
1answer
81 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 ...
3
votes
1answer
59 views

Project Euler #357: Prime generating integers

Project Euler Problem 357 asks: Consider the divisors of 30: 1,2,3,5,6,10,15,30. It can be seen that for every divisor d of 30, $$d+30/d$$ is prime. Find the sum of all positive integers n ...
5
votes
1answer
63 views

Goldbach conjecture solution finder

The Goldbach conjecture says: any even number greater than two can be represented by the sum of two prime numbers. G(n) = { (p1, p2) | p1 + p2 = n, p1 and p2 are prime numbers with p1 < p2 } ...
7
votes
1answer
107 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 ...
1
vote
1answer
86 views

A faster way to compute largest prime factor (Again, but a lot better)

I came up with this code after implementing the feedback given by @200_success. The previous one (A faster way to compute the largest prime factor) tested my patience, but still failed to give the ...
9
votes
4answers
2k views

A faster way to compute the largest prime factor

I am self-learning js and came across this problem(#3) from the Euler Project The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? ...
1
vote
2answers
38 views

Segmented Sieve Spoj

I tried(trying...) to solve the SPOJ prime number problem PRIME1 so i learned and implemented Segmented Sieve correctly but this program works in time for 10^8 but getting Time limit exceeded (TLE) ...
2
votes
3answers
203 views

Determining primality by removing select composits

Calculating many remainders for each prime and composite consumes more time. I use a factoring function to find factors of single values. When I use a factoring function to find lists of primes, I ...
4
votes
2answers
127 views

Efficient Prime Number Generator in c++

I am trying to make an efficient prime number calculator. I've seen ones that can go up to close to 1 trillion in right around 4 hours, however I left mine on overnight and didn't get anywhere near ...
8
votes
1answer
410 views

Prime factors and perfect square

I want to convert an integer to a perfect square by multiplying it by some number. That number is the product of all the prime factors of the number which not appear an even number of times. Example ...
3
votes
1answer
68 views

Generate two random primes and find their totient

I am supposed to make a basic RSA encryption/decryption code, where I am only given e. I wrote this code to randomly generate two primes and then find their totient. But the totient is supposed to ...
6
votes
1answer
216 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^...
4
votes
1answer
42 views

Rust version of basic functional prime stream - can this be made less clunky?

I'm looking at implementing the basic functional not-quite-Eratosthenes prime stream in Rust. I like to try it when I start learning a language. Here's the bog standard Haskell version: ...
1
vote
2answers
73 views

Work out largest prime factor of a number

I am trying to get better at problem solving, so I am going through challenges on Project Euler. Problem: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of ...
3
votes
1answer
76 views

Fast Factorisation (Python Implementation)

An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is \$O(n^{1/2})\$, the best case would be \$O(\log(n))...
2
votes
2answers
423 views

The next prime number in Python

I have written a solution to a DM::OJ exercise to find the next Prime Number after a given number (input). I'm seeking to optimize it so that it will run for any number up to ...
1
vote
3answers
158 views

Kattis prime reduction challenge

I am solving the Prime Reduction challenge on Kattis. Consider the following process, which we’ll call prime reduction. Given an input x: if x is prime, print x and stop factor x into its ...
2
votes
1answer
126 views

Faster Sieve of Eratosthenes

This is an implementation of the Sieve of Eratosthenes : It takes advantages of the fact that all primes from 5 and above can be written as 6X-1 or ...
0
votes
2answers
54 views

Euler Project #3 Largest prime factor timeout

I have been recently trying my hands on Euler's Project through HackerRank and got stuck with project #3 where you have to find the Largest Prime Factor. Question: The prime factors of 13195 are 5, 7,...
5
votes
1answer
50 views

Find primes that are also primes when its digits are rotated

The program below is meant to find all of the fare prime numbers under a user specified value. A fare prime being a number that when its digits are rotated, each combination makes a prime number. An ...
3
votes
2answers
86 views

Project Euler #7: Nth prime number

I was solving Project Euler #7 on Hackerrank but for two cases, execution time is more than 2 sec. Can you help with optimizing? I'm new to programming. ...
0
votes
1answer
39 views

Naïve Prime Factorization in Clojure Pt. 2

After my last review request, I decided to try and make a "tree" visualization, and thought that I could benefit from making find-prime-factors lazily produce prime ...
1
vote
0answers
41 views

Naïve Prime Factorization in Clojure

I saw a question about prime factorization on Stack Overflow and realized I had never attempted it before. This was what I ended up with after some playing around and tweaking. I'd like improvements ...
8
votes
1answer
206 views

Find “prime polynomials” for a user's given prime, bounds, and degree

Very amateur programmer and first-time poster here. The program I wrote asks the user for a prime number, a lower and upper bound, and a degree (all of these are integers). I want to generate a list ...
-2
votes
1answer
148 views

Finding all prime factors of a number in C# [closed]

I recently wrote a function to find all prime factors of a number and I'd like to know how to improve it. I'm particularly interested in how I can redesign anything to make it more efficient, mainly ...
5
votes
1answer
192 views

A Rust crate with both `main.rs` and `lib.rs` performing primality checking

Introduction I decided to get my feet wet in Rust by going ahead an implementing a full crate with the tests, documentation, and all other accompanying stuff. This is a toy implementation of a ...
2
votes
2answers
73 views

Prime engine: generation, primality, factorization

I've just written my first C# class, so I'm looking for some feedback before I go and write more code. The goal of the code is to provide a Singleton-like class to deal with common operations on the ...
3
votes
1answer
328 views

Prime factorization in Python

Beginner programmer here. What can I improve in my code? Are there things I'm doing wrong or are there easier ways of doing what I did? ...
0
votes
1answer
92 views
2
votes
1answer
33 views

Testing a probabilistic prime-testing algorithm that may fail

I have implemented Pollard's Rho algorithm in Java. Due to the nature of it there is a small chance for it to fail (have not seen it happening yet). Since I do not ...
2
votes
1answer
64 views

Generation of products of power

Given positive integers a,b,c and limit, I want to generate all products having the form $$p^aq^br^c \leq limit$$ less than limit (where p,q,r are distinct primes). a,b and c are not necessary ...
4
votes
2answers
123 views

Euler Problem 7 (finding the 10001st prime) in Powershell

I am having issue making this code more efficient. The problem to be solved is as follows: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. ...
2
votes
2answers
182 views

Project Euler Problem 37 in Python

Project Euler Problem 37 asks: The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797,...
0
votes
3answers
153 views

Display a number as a product of its prime factors

Task: Link to original problem :https://www.spoj.com/problems/FACTCG2/ The task in this problem is to write a number in a multiplication of prime numbers separated by “...
0
votes
2answers
57 views

Finding primes from random integers

I was hoping I could get some help making my code more efficient. I'm a math major taking an Intro to Programming class, and I was asked to write a C program that generates: A text file named ...
3
votes
1answer
114 views

Program that finds prime numbers in a specific range

I'm kinda new to programming, and as a solution to an exercise, I made a program to find prime numbers in a range. It runs just right for small ranges of numbers, but for this exercise we are given a ...
1
vote
2answers
78 views

Prime factorization program

Compute the prime factors of a given natural number. A prime number is only evenly divisible by itself and 1. Note that 1 is not a prime number. My solution will catch every prime up to and including ...
3
votes
2answers
129 views

Sieve of Eratosthenes in Rust

This is a relatively simple implementation of the Sieve of Eratosthenes in Rust. The main objective is to find the \$n\$th prime quickly when \$n\$ might grow to huge numbers. ...
20
votes
3answers
3k views

Checking if a number is prime in NASM Win64 Assembly

I'm just learning Assembly. This program is a simple attempt to determine if a given number is prime or not. Any advice and all topical comments on code optimization and conventions is appreciated! ...
0
votes
2answers
81 views

Prime number generation - SPOJ

This is a program to generate prime numbers for a given range. The sieve of Eratosthenes algorithm was implemented, but still the SPOJ says time limit exceeded. Where can some optimizations be made? ...
3
votes
1answer
53 views

C++/STL Prime tuples (twin, cousin, sexy) up to the given limit

As I'm mastering STL I wrote a solution for generating all the prime tuples of the form (p1,p2) where "twin" means p2-p1=2, "...