# Tagged Questions

61 views

### Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
148 views

### The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
37 views

### Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
69 views

93 views

### Are there any algorithms to check if a big number is a prime number?

I want to check if a given number is a prime number. Are there other ways than brute-force? It should be fast and work with bigger numbers (>1.000.000).
161 views

### Special number near $5^{5^3}$

I search the number nearest to $5^{5^3} = 5^{125}$, which is product of two $44$-digit primes. The direct method is : Begin with $N = 5^{125}$. Increase $N$ until the desired number is found. ...
347 views

### Random Primes between 4000000000 and 4294967291 (C++)

What is an efficient way to find a random prime between $4000000000$ and $4294967291$ in C++? This is what I wrote, but it is ridiculous: ...
164 views

### Making fermat's little theorem for composite numbers the ultimate test.

It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem ...
67 views

### General term of this sequence

I wanted to know the General term or the function to generate this sequence I found on OEIS. It is the number of ways to express $2n+1$ as $p+2q$; where $p$ and $q$ can be odd prime number and even ...
84 views

### Find all expressions of a prime as a sum of four squares

Does anyone know an efficient algorithm to compute all solutions of $$x^2 + y^2 + z^2 + w^2 = p$$ where $x, y, z, w \in \mathbb{Z}$ and $p \in \mathbb{P}$? By efficient I mean linear on the number ...
144 views

### finite field to rational fraction

Suppose I have a number $n\in\mathbb F_p$, i.e. an element of the finite field obtained by arithmetic modulo some (odd) prime $p$. I'm looking for a way to find a simple description of $n$ as a ...
300 views

### Proof of Prime Maker Conjecture

In my mind the following conjecture is true: Prime Maker Conjecture I call a number $n$ factor-resistant to $q$ if $q\not\mid n$. Considering $n$ as a composite number, the idea is to make $n$ ...
24 views

### If I am checking for $s$ divides $n$ on the interval $S = [3, n-x]$, how large can I make $x$ to ensure I have verified $n$ is prime?

$\forall x \in \mathbb{Z}^+$, $x > 1 \longrightarrow x-2$ does not divide $x$ I have not yet proven this, which might be a good aside for my discrete math. One of my current assignments in ...
172 views

### How to prove there is no algorithm for a problem e.g. generating next prime?

Say I want to find the next prime directly without a test. AFAIK there is no known formula. Is it possible that since we've failed to find a formula, then we might be able to prove that there is no ...
521 views

### Determining the next Twin Prime?

A really simple I question I guess. Is there an algorithm or method such that given an integer $N$ there is a way to determine the next twin prime pair greater than $N$? If yes, then could you please ...
2k views

### How many all prime numbers p with length of bits of p = 1024 bits?

How many all prime numbers p with length of bits of p = 1024 bits? And is there any algorithm which generates all prime numbers p?
215 views

### Is the product of 2 unique prime number unique?

I am wondering if I take the product of 2 unique prime numbers, and will the product be unique ? any chance to have collision ? I mean will any other 2 unique prime numbers have the same product ? ...
290 views

### Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If CramÃ©r's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
336 views

### Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
51 views

### Is there any way to split a number with multiplication of some prime number

I am looking for an algorithm which helps me split a number $N$ as such: $$N=p_1^a p_2^b \cdots p_n^z$$ where $N$ is the given number, $p$ is prime numbers smallest to greatest, and $a,b,\cdots,z$ ...
658 views

### What prime number generating algorithms are used?

You sometimes hear bout these huge prime numbers (RSA prime number challenge comes to mind) and I was curious about what algorithms or formulas prime-number generators use in practice ? For example in ...
817 views

### Expressing a Non Negative Integer as Sums of Two Squares

I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ...
177 views

### What is the fastest algorithm to check if a number has only 3 divisors?

Which is the fastest way to check if a number has only 3 unique factors ? Any help will be highly appreciated?
94 views

### Searching for prime candidates

For some additional excitement, I've been searching for primes $p \gg q = 104729$, where $q$ is of course the ten-thousandth prime. It seems that the best way to search for prime candidates $p$ is to ...
1k views

### Get numbers that have only 2,3 and 5 as prime factors

I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number. ...
1k views

### Algorithm to generate a prime number which is n-digits long

Is there an algorithm which, given the number of digits n, generates a prime number which is n-digits long, in polynomial time complexity?
3k views

### Pollard-Strassen Algorithm

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all ...
94 views

2k views

### Why choose a prime number as the number of slots for hashing function that uses divison method?

The division method is one way to create hash functions. The functions take the form: h(k) = k mod m Where k is a key and m is the number of slots Edit: If this is my hash function why should ...