Questions tagged [primes]

The tag has no usage guidance.

121 questions
Filter by
Sorted by
Tagged with
53 views

Is this how I could come up with the time complexity for the Sieve of Eratosthenes?

So here is how I tried to come up with the time complexity for the Sieve of Erast. According to Wikipedia it is $O(n \; \text{log} \;\text{log}\;n)$. I got $O(n \; \text{ln}(\sqrt{n}))$ Here is what I ...
• 31
1 vote
45 views

Is it theoretically possible to discover a prime-checking algorithm with the time complexity of $O(\ln n)$ or $O(1)$?

I was just playing around and was trying to make a algorithm for primality testing with the target time complexity of $O(\ln n)$. I'm new to the concept of time complexity and was wondering is it ...
• 11
144 views

O(n) algorithm to find primes up to n

I don't know the name of this algorithm, but anyway it was interesting to share (btw Linear sieve, Sieve of Atkin and Sieve of Pritchard performs better) The main idea is to use the Fundamental ...
305 views

Testing whether a number (N) is prime or not can be made very fast but it will require storage space

Testing whether a number (N) is prime or not can be made very fast but it will require storage space. If there is a central repository that stores all prime numbers found till now and if there is a ...
751 views

Is Determining the Number of distinct Prime Factors Polynomial?

Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. ...
• 55
256 views

What is the time complexity of this algorithm of finding all prime numbers?

I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called. ...
74 views

How to allocate memory for prime numbers

I was working on an algorithm to find prime numbers, and I needed to allocate memory for each prime number that I found so far. I will do a search up to N and need to allocate all memory in advance. I ...
• 103
221 views

A new algorithm for determining if a number is prime or not

This approach has been on my mind for quite some time. I did come up with it myself, I searched some methods for determining prime numbers but never came across anything similar to this. ...
1 vote
43 views

Is Miller-Rabin not a suitable algortihm for the RSA key generation or am I missing something?

I'm trying to recreate the RSA key generator, from what I understood you must create two prime numbers of 256 bytes long, p and q...
• 11
200 views

...
• 13
99 views

72 views

Solve SUBSET SUM for Reciprocals of Primes

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
494 views

Time complexity of Sieve of Eratosthenes [closed]

Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?
• 111
1 vote