Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
12 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 ...
5
votes
1answer
173 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^...
3
votes
1answer
29 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
39 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 ...
2
votes
1answer
46 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
75 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
83 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
70 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
49 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
45 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
76 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
0answers
18 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
24 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
195 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
74 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 ...
4
votes
1answer
113 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
105 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
70 views
2
votes
1answer
29 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
63 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
1answer
60 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
102 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
102 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
56 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 ...
2
votes
1answer
102 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
77 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
98 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
64 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
51 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, "...
-1
votes
1answer
317 views

For pairs of elements, count the ones whose XOR value is a sum of two primes [closed]

An array is given with 'n' Values ( n <= 10^5 ) ; we have to calculate xor of each pair of elements and count those pairs whose xor can be written as sum of two prime numbers with the same parity(...
3
votes
2answers
156 views

Calculate divisors using prime factorization

For learning purpouses I wrote a class that is supposed to find all divisors for a given integer. My class makes use of primes and prime factorization to speed things up a bit. What can I improve in ...
-1
votes
2answers
134 views

Largest prime factor function

I have written a function which finds the largest prime factor of some number. This function works but the problem is that it is too slow. For instance, when I enter 600851475143 as a parameter, the ...
7
votes
2answers
625 views

alternating Fibonacci and prime series

The task is to print the following series 1 2 1 3 2 5 3 7... The elements at odd positions are Fibonacci series terms and the elements at even positions are ...
4
votes
1answer
124 views

Prime pair set finder (Project Euler problem 60)

I made a code that can find the prime sets: The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For ...
2
votes
1answer
201 views

Are numbers prime multithreading

I'm trying to learn some multithreading and this seems like a good example, want to apply this to frustum culling later. The goal is to find prime numbers in randomly generated vector of numbers. ...
0
votes
1answer
39 views

Printing all the factors as well as the prime factors of a given number using Python 2.7.x

Okay here is my maiden attempt at programming using Python 2.7. I need help or feedback on this code: How do I know about the processing cycles this program consumes? How do I implement this idea ...
7
votes
1answer
300 views

Printing factors and prime factors of a number

I am a 46 year young newbie trying to learn programming for fun and adventure. I do this in my free time. Some very nice gentlemen on stackoverflow have sent me here. I wish that someone could review ...
3
votes
1answer
64 views

Spoj-Prime Generator

Question- Generate all prime numbers between two given numbers. https://www.spoj.com/problems/PRIME1/ My attempt- I used segmented sieve method. ...
5
votes
2answers
486 views

Euler problem 3: largest prime factor of the number

I have been trying to learn Python and just solved Euler Problem 3: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I am looking ...
4
votes
1answer
128 views

Sieve of Eratosthenes in Python

This is yet another take in Python for the infamous Sieve of Eratosthenes. I am a beginner in Python so any criticism is highly appreciated. ...
10
votes
4answers
930 views

Calculating primes until a user-given value

I am new to C# programming. I wrote a little program in C# to calculate all primes until a user-given value. Ignoring the lack of computing power I wrote this program to handle theoretically very huge ...
4
votes
2answers
121 views

Show all primes in go

I'm trying to go through Adrian simple programming tasks; Elementary task 8 It's basically asking for an infinite loop to print every prime number as it finds it. Are there too many ...
3
votes
1answer
252 views

Prime number sieve in Standard ML

As practice, I have written a prime number sieve in Standard ML. It works in a pretty straightforward way: The list of known primes starts with just 2. Starting with 3, check whether each odd ...
15
votes
5answers
5k views

Python 3: Why is my prime sieve so slow?

I've implemented the sieve of Eratosthenes in Python 3 as follows: ...
2
votes
1answer
126 views

Project Euler: Find 10.001st prime

I have just started learning C# and decided to do some problems from Project Euler. I wrote a code to find 10 001st prime and I thought it would be cool optimize it to make it as fast as possible. How ...
2
votes
0answers
66 views

Haskell function to generate prime numbers up to argument [closed]

I made a function to generate a list of prime numbers using list comprehensions. Here it is: ...
2
votes
1answer
169 views

Prime numbers generator

This is a prime numbers generator class, loosely based on the sieve of Eratosthenes. It is supposed to generate a decent quantity (i.e. millions) of prime numbers. ...
1
vote
0answers
78 views

Get prime divisors of an Int32 using a wheel

I recently played around with prime factorization using a prime wheel. Much of the heavy lifting is done by the PrimeWheel class. I think the implementation is ...