Hot answers tagged prime-numbers
23
If not assumed otherwise m and n can be whatever, so you can do e.g. this :
Solve[ Prime[n] + Prime[m] == 100, {n, m}, Integers]
{{n -> 2, m -> 25}, {n -> 5, m -> 24}, {n -> 7, m -> 23}, {n -> 10, m -> 20},
{n -> 13, m -> 17}, {n -> 15, m -> 16}, {n -> 16, m -> 15}, {n -> 17, m -> 13},
{n -> 20, m ...
7
Might be faster to do batches by checking for nontrivial gcds. Below I group 100 primes into each batch, take their products, and do a gcd computation until finding that there is a divisor. The example sieves a million primes.
random = RandomPrime[10^1000];
list = Table[k random + 1, {k, 1, 2000}];
pprods = Apply[Times, Partition[Prime[Range[10^6]], 10^3], ...
7
initial side note: As J.M. correctly points out this is not an efficient implementation and serves only to illustrate behavior similar to the Python function all.
If you are looking for a similar definition to the Python code you give, then you could use this:
isPrime[n_] := And @@ Table[Mod[n, i] != 0, {i, Range[2, n - 1]}]
This creates a table of ...
6
I had a clever idea for how to do this using LatticeReduce[], but I decided to code up the Smith-Cornacchia algorithm first to bench mark against, and it was effectively instant for inputs in your range. Here is a sloppy implementation. In particular, I am embarrassed by applying Divisors[] to something which is computed as a product. However, the result is ...
6
Given a large n, to find k largest primes below n (as well as above) the best approach uses NextPrime (it has been added to Mathematica 6) :
NextPrime[n] gives the next prime above n.
NextPrime[n,k] gives the k-th prime above n. If k is negative it gives k-th largest prime below n.
k need not be a single number but it may be a list of ...
6
Addendum
If you just want the greatest 10 primes less than M, you can start from Prime[PrimePi[M]-9]. By doing so, you gain a speed increase of 2 orders of magnitude when M = 100000.
M = 100000;
m = PrimePi[M]
AbsoluteTiming[Table[Prime[k], {k, m - 9, m}]]
9592
{0.000171, {99877, 99881, 99901, 99907, 99923, 99929, 99961, 99971, 99989, 99991}}
Now ...
3
Just a small change and you get a free speedup : rather than looping over 10000 and then calculating Prime[p] each time, do a Prime[Range[10000]] once and for all.
SeedRandom[6];
random = RandomPrime[10^1000];
initialList = Table[k random + 1, {k, 1, 2000}];
list = initialList;
counter = 2000;
{elapsedOP, resultOP} = Do[Do[If[Divisible[n, Prime[p]], list = ...
3
Quote from MSieve (one of the more popular factorization programs):
On a fast modern CPU, a 110-digit QS factorization takes nearly 120 hours for Msieve.
A 100-digit one should be significantly less than that. So, no, it does not take 100 years.
The trouble you are having fitting your data is not that there are too few points, but the distribution of ...
Only top voted, non community-wiki answers of a minimum length are eligible
