Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
56 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. ...
Akash Ram's user avatar
0 votes
1 answer
59 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 ...
Jip Helsen's user avatar
-1 votes
2 answers
115 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. ...
Akash Ram's user avatar
0 votes
0 answers
43 views

Universal hash functions and prime number modulus scheme

Definition of a universal hashing function $h: U \rightarrow[m]$ (where $[m]=\{0, \ldots, m-1\}$) is that for any given distinct keys $x,y \in U$, when $h$ is picked at random (independently of $x$ ...
Jung's user avatar
  • 101
1 vote
0 answers
39 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...
chyxo's user avatar
  • 11
0 votes
0 answers
37 views

Minimum even goldbach partitioning

The following is an excerpt taken from Oliveria's paper "Empirical verification of the even goldbach conjecture...", it gives an alternative segmentable minimal interval partitioner for the ...
Kevin Perez's user avatar
0 votes
1 answer
118 views

search for the next prime number more efficiently?

...
ant0982's user avatar
  • 13
3 votes
1 answer
82 views

Counting integers $n \leq x$ with a given prime signature

Given is a prime signature $S$ and an integer $x$. The task is to count how many integers $n$ exist such that $n \leq x$, and if $n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...$ then $S = (k_1,k_2,k_3,......
MC From Scratch's user avatar
1 vote
1 answer
68 views

Best known deterministic algorithm for generation of any (non random) n-bit prime?

Sometimes we need some prime number with certain minimum size for modular algorithm. For practical purposes we can precompute (using fast randomized algorithms) table of some primes for range which ...
Somnium's user avatar
  • 275
2 votes
2 answers
350 views

Fast identification of prime power factors?

For a given integer exponent $e$, I want to identify all factors of an integer $n$ which are of the form $p^{e}$, where $p$ is a prime. So, for $e = 1$, this is equivalent to getting the unique prime ...
Logan R. Kearsley's user avatar
0 votes
2 answers
98 views

Find the largest possible number not larger than some integer N and is the product of K consecutive primes

Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố) Additional conditions: N is a positive integer in range [1, 2^64 - 1] K is a positive integer in range [3, 10] ...
Minh Đức Hoàng's user avatar
1 vote
2 answers
155 views

Combinational logic check if bits is prime

I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not. For example given input fixed 8-bit that will produce 1-bit output. 00000101 will ...
Muhammad Ikhwan Perwira's user avatar
0 votes
2 answers
264 views

Integer/prime factorization to 3 SAT

So essentially as the title says, I just want to understand how its done. I have a light idea from my own research, but its failing at one point, and I feel it maybe due to crucial point missing in my ...
khaled sabek's user avatar
1 vote
2 answers
145 views

$L_p$ contains all binary strings whose value as binary number is prime. What are those values?

Context-: https://math.stackexchange.com/questions/1600257/determining-if-a-binary-string-represents-a-prime-integer Confused text-: The problem of testing primality can be expressed by the language ...
silfeg's user avatar
  • 51
12 votes
8 answers
2k views

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
Trev's user avatar
  • 284
1 vote
0 answers
55 views

Find array of coprime integers whose average is maximized

I am creating a class to store large integers in a residue number system. I want each "integer" to be 4-12GB in size and be comprised of 64-bit moduli. These moduli must be pairwise coprime ...
Brandon Feder's user avatar
1 vote
0 answers
32 views

Postponed sieve algorithm with start logic [closed]

Based on the answer by Will Ness, I've been using a JavaScript adaptation for the postponed sieve algorithm: ...
vitaly-t's user avatar
  • 111
0 votes
1 answer
61 views

How to get the numbers in the Sieve of Eratosthenes with wheel factorisation?

I'd like some help with figuring out the algorithm for the Sieve of Eratosthenes with wheel factorisation. Specifically, I need help figuring out if it's possible to convert between an index and the ...
nicoty's user avatar
  • 111
6 votes
2 answers
2k views

How can we count the number of pairs of coprime integers in an array of integers? (CSES)

For reference, I am trying to solve this CSES Problem. The problem basically states that given up to $10^5$ positive integers in the range $[1, 10^6]$, find the number of pairs of those positive ...
Christopher Miller's user avatar
2 votes
1 answer
31 views

How to approximate big composite number factors?

There is a big 1024-bits number A that was obtained by multiplying two numbers B and C.Are there any ways to get first numerical digits of these numbers? How example: ...
Alexandr Dorofeev's user avatar
1 vote
1 answer
58 views

Is it true that PRIMES are in SPARSE?

I'm wondering if PRIMES, the language of all prime numbers represented in binary, which is $\{10, 11, 101, 111, 1011, 1101, ...\}$, belongs to the SPARSE class, a set of all sparse languages, that is, ...
Captain Trojan's user avatar
0 votes
1 answer
423 views

Four functions problem

This is not from online contest Hi guys, a friend of mine recently give me this problem that I couldn't figure out an effective way to solve it. Four functions You are given four functions $$ \begin{...
Loc Truong's user avatar
0 votes
0 answers
115 views

File compression using prime numbers

My theory take a file examplesize:(3GB) convert said file to a number divide that number by a large prime number example:(2^82,589,932 · (2^82,589,933-1))[2018 Dec 07] get the quotient and the ...
Steven's user avatar
  • 1
1 vote
1 answer
101 views

RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1

I want to make a following proof but I got some difficulties with it. Would be super if you people have any tips / advises. Introduction: Let (N,e) be our public key and (N,s) our private key with $N=...
Florian Bauer's user avatar
1 vote
1 answer
88 views

optimizing the calculation of $\sum^n_{k=2} p(\Omega(k))\Omega(k)$

I want to optimize an algorithm for calculating $g(n)=\sum^n_{k=2} p(\Omega(k))\Omega(k)$ where $$ p(n) = \begin{cases} 1 &\text{if $n$ is odd} \\ -1 &\text{if $n$ is even} \end{cases}$$ and ...
razivo's user avatar
  • 113
2 votes
0 answers
34 views

Central Trinomial Coefficients best time complexity

What is the fastest known time complexity for computing central trinomial coefficients? Let $C_n=1,1,3,7,19,51,...$ (OEIS A002426) denote the coefficient of $x^n$ in $(x^2+x+1)^n$ starting at $n=0$. ...
J. Linne's user avatar
  • 141
1 vote
4 answers
435 views

Determine the number of elements that is divisible by a prime number in an array

I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers. For each of the prime numbers, I want to know how many numbers in the first array are divisible by ...
Curious student's user avatar
0 votes
1 answer
93 views

How efficient of this prime sieving algorithm?

I just found there is an old program of mine where I implemented the following prime sieving algorithm: ...
Kindred's user avatar
  • 314
0 votes
1 answer
111 views

Prime factorization for compressing streams of random numbers

We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea: Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number ...
Yamahari's user avatar
  • 203
1 vote
1 answer
176 views

An algorithem for finding the number of primes of the form 4k+3 under some n

I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 ...
sean python's user avatar
2 votes
0 answers
70 views

Partition a set of factors so that the difference between products is minimized

I'm sure this problem must be well-known... Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the ...
Quuxplusone's user avatar
1 vote
1 answer
71 views

While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test?

While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity ...
Mohsin Shaikh's user avatar
0 votes
1 answer
76 views

Is the complement of this decision problem in $P$?

Are there any two primes that are NOT a factor of $M$ that multiply up to $M$? Fact: Any two primes that multiply up to $M$. Must be factors of $M$! Thus because of the fact above an $O(1)$ algorithm ...
Dingle Berry's user avatar
0 votes
0 answers
31 views

Algorithm always provide a $2$_$sum$ with at least ONE prime? In polynomial-time?

Function Problem: Given $N$ find a $2$_$sum$ that uses at least $ONE$ prime. Fact: Prime Gaps grow logarithmically on average. And, in worst case if memory serves correct it grows with a bounded ...
Dingle Berry's user avatar
1 vote
2 answers
497 views

Fastest algorithm for finding the number of primes in a range

Is there an algorithm for finding the number of primes in a given range $[N, M)$ that works in time linear to $M-N$? For context, $N$ and $M$ can go up to $10^{10}$, but the distance between N and M ...
pblpbl's user avatar
  • 43
1 vote
0 answers
102 views

how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?

I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at ...
User1396's user avatar
0 votes
3 answers
117 views

Primality testing algorithm

Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ ...
User Not Found's user avatar
3 votes
1 answer
213 views

Efficiently prime factorising an integer with an oracle

Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns ...
user avatar
0 votes
1 answer
48 views

What computational model supports arbitrarily sized integers?

I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine. So what is the model that addresses ...
MathCrackExchange's user avatar
0 votes
1 answer
293 views

How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?

How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the ...
Mateusz Mazurek's user avatar
2 votes
1 answer
414 views

Prime checking and factorization with just bit cheking

I've read about some methods of prime factorization like here and here. However, I'm wondering: what can we do in prime factorization with just some bit manipulation and without other variables/...
ChocolateOverflow's user avatar
1 vote
1 answer
148 views

Is SEMIPRIME in P?

The title says it all: is there a deterministic polynomial time algorithm that tests for semiprimality? (A number $N$ is a semiprime if it is the product of two primes.) I don't understand the ''...
Olivier Bégassat's user avatar
1 vote
2 answers
618 views

Pumping Lemma with Prime Number [closed]

$\text {Could someone please help me with this proof: }$ $L:=\left\{a^{n} d^{m} b^{k} | n, m, k \in \mathbb{N} \wedge m \text { is a prime number}\right\}$ $\text {Maybe we can say, that } w=a^{n}d^{...
mathflower's user avatar
3 votes
1 answer
55 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 (...
SmashTheStack's user avatar
0 votes
1 answer
471 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?
kevin's user avatar
  • 111
1 vote
1 answer
89 views

Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?

I was programming the AKS primality test, and I have two questions. Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)? Is it correct that if gcd(n, k)>1, then binomial(n, k)>0 (mod n)?...
wow's user avatar
  • 11
0 votes
0 answers
160 views

Is the Time Complexity of Trial Division Exponential? [duplicate]

I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing ...
Marcel Mazur's user avatar
1 vote
1 answer
208 views

What is the complexity of this prime trial division algorithms?

I have two algorithms. What are their time complexities? The first algorithm checks the modulo of all odd integers from $3,5,...\sqrt{n}$. The second algorithm generates a list of prime from $2,3...,\...
Papaj Chan's user avatar
0 votes
1 answer
43 views

Coprimes satisfying a pair

We know that number of coprimes less than a number can be found using Euler's totient function. But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ ...
Manoharsinh Rana's user avatar
2 votes
0 answers
301 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
Gokul E's user avatar
  • 125