# Tag Info

## Hot answers tagged prime-numbers

24

PrimeQ and FactorInteger use different algorithms. In general asking whether a number is prime is an easier problem than finding its factors. To quote the documentation, "PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test", while "FactorInteger switches ...

20

The built-in functionPrimeOmega gives you the number of prime factors and counts multiplicities. Therefore, this can easily be used to give you semi-primes as you have defined them: With[{r = Range[50]}, Pick[r, PrimeOmega[r], 2]]

19

A Trace reveals the problem: Product[If[PrimeQ[p], (p^2 + 1)/(p^2 - 1), 1], {p, 2, Infinity}] // Trace (* {Product[If[PrimeQ[p], (p^2 + 1)/(p^2 - 1), 1], {p, 2, Infinity}], {{PrimeQ[p], False}, If[False, (p^2 + 1)/(p^2 - 1), 1], 1}, Product[1, {p, 2, Infinity}], 1} *) The If[] statement is evaluated before the Product. In turn PrimeQ[p] ...

18

In general Mathematica cannot compute symbolically infinite sums over primes because of the lack of appropriate mathematical tools. However there are infinite products over primes which are basically well understood on the mathematical level. One famous example is the Euler formula for the Riemann zeta function, one of the most beautiful (and mysterious ...

17

I want to answer the part of the question, "How could my son be expected to find a prime factor?" Well, this depends on what your son has been taught, of course. A first thing to notice is that, since 99! is divisible by every prime less than 99, 99! - 1 is not divisible by any of those primes; so 101 is the smallest prime which could be a factor of it. So ...

16

You could use FactorInteger to find out whether or not there are exactly two primes building up a number: SemiPrimeQ[n_Integer] := With[{factors = FactorInteger[n]}, Total[factors[[All, 2]]] == 2 ] The rest is easy: Select[Range[50], SemiPrimeQ] (* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *) And for those who like inline ...

16

I believe this is correct, and very fast: fn[x_Integer, n_Integer] := Complement[Range @ x, Join @@ Range[#, x, #]] & @ Prime @ Range @ n Test: fn[10000, 1223] {1, 9929, 9931, 9941, 9949, 9967, 9973} It seems I am a bit late to return to this problem and Simon Woods already provided a memory optimized approach. His sieve is comparatively fast ...

16

This is competitive with Mr Wizards code and seems faster in some cases: fn2[x_Integer, n_Integer] := Module[{y = Range @ x}, (y[[# ;; x ;; #]] = 0) & /@ Prime[Range @ Min[n, PrimePi @ x]]; SparseArray[y]["NonzeroValues"]] AbsoluteTiming[fn[10000, 1223];] (* {0.004000, Null} *) AbsoluteTiming[fn2[10000, 1223];] (* {0.010001, Null} *) ...

16

Culling elements from lists may done several ways, such as with Cases, Select, and Pick. Cases and Select seem quite similar when culling elements from level 1. The documentation for Select shows that the following are equivalent: Select[list, f] Cases[list, x_ /; f[x]] This, too, is equivalent: Cases[list, _?f] The functions Condition (/;) and ...

14

Turning my comment into an answer, One of the tests performed by PrimeQ for machine-sized integers, namely Miller-Rabin using up to the first 12 primes as bases (as of version 10) has been proved correct for integers up to $2^{64}$ (in fact, the smallest number which that test falsely declares a prime is known to be $3186 65857 83403 11511 67461.$) Of ...

14

If you need all the primes that are twin primes up to n then. TwinPrimesUpTo[n_] := Select[ Most@NestWhileList[ NextPrime, Prime[1], # <= n & ] , (PrimeQ[# + 2]||PrimeQ[# + 2]) &] It was pointed out by @KennyColnago in other answer that it's customary to count the number of pairs of twin primes, in which case a list of the ...

14

As people on the comments pointed out this may be a problematic in various ways, but if all y-values of your points are primes, this can be accomplished with ScalingFunctions option. PrimePi is an inverse of the Prime function, and you list both to guide ListPlot: maxPrimeIndex = 25; maxPrime = Prime[maxPrimeIndex]; Flatten[(Partition[ Riffle[Flatten[...

13

out = Select[MatchQ[IntegerDigits[#], {___, 5, ___, 4, ___, 3, ___}] &]@ Prime[Range[50000]]; Length@out 1588 Short@out {1543, 2543, 5413, 5431, 5437, 5443, 5483, 5743, 5843, 8543, <<1568>>, 599243, 599413, 599843, 601543, 602543, 605413, 605443, 605543, 610543, 611543} If you need just the count: count = Count[{___, 5, ___, 4, ___, 3, ...

12

I prefer Bold and Larger in Style: Animate[ Grid[ Partition[ Table[ Style[i, Bold, Larger, If[i > j, Black, If[ PrimeQ @ i, Blue, Gray]]], {i, 100}], 10], Spacings -> {1, 1}], {j, 0, 100}, Paneled -> False] but if you like delete from the ...

12

A naive approach would be this: primePower[n_] := Count[ Range @ n, _?PrimePowerQ] This function works well however it might be very inefficient for large n. It takes a bit to evaluate e.g. primePower[10^6] 78734 which is only a little bigger than PrimePi[10^6] 78498 The latter is much more efficient since it uses advanced algorithms for counting ...

11

I cannot take credit for this, but here is a rather interesting and compact implementation that I found somewhere: F[n_] := {Re[#], Im[#]} & /@ Fold[Join[#1, Last[#1] + I^#2 Range[#2/2]] &, {0}, Range[n]] G[n_] := Table[#[[Prime[k]]], {k, 1, PrimePi[n^2/4 + 1]}] &[F[n]] ListPlot[G[500], AspectRatio -> Automatic, Axes -> None, Frame -> ...

11

In a nutshell, factoring integers is a harder problem than determining primality. This seeming asymmetry is exploited as a component in modern computer security systems (in the form of the RSA cryptosystem). Determining primality has long been known to be doable in polynomial time using a variety of probabilistic algorithms, many of which (as mentioned by ...

11

Take a look at IntegerPartitions, although it relies on brute-force enumeration that is unlikely to scale well. f1[n_] := IntegerPartitions[n, {2}, Prime @ Range @ PrimePi @ n, 1] f2[n_] := Length @ IntegerPartitions[n, {2}, Prime @ Range @ PrimePi @ n] Test: f1[3412] {{3407, 5}} f2[3412] 43 Further experiments Anton Antonov's recent answer ...

11

Prime and IntegerDigits are Listable, ___ (i.e. BlankNullSequence) is a pattern object that can stand for any sequence of zero or more expressions. This is a nice approach and quite fast: Length @ Cases[ IntegerDigits @ Prime @ Range @ 50000, {___, 5, ___, 4, ___, 3, ___}] 1588 Remarks This metod and kglr's operator approach ...

10

Artes's answer is just fine. This variation works as follows. When you click on a number, the background of that number turns yellow and that of each of its divisors turns light blue. DynamicModule[{s = 101}, Grid[Partition[Dynamic@Button[Style[#, 16], (s = #), Background -> Which[ # == s, Yellow, Divisible[s, #], LightBlue, True, White], Appearance -...

10

There are several problems with your code. The first one is that you are missing a couple of semicolons to suppress output and delineate substatements in a compound function. The second problem is that you are trying to assign a new value to x within the function definition. This doesn't work. x already has the value of whatever number you give. You need ...

10

The problem with your code is that N[Product[...]] calls NProduct[...] which turns integers into reals before Prime can evaluate, causing the error: See Details and Options section of documentation of NProduct. For your calculation, you actually do not need these. It looks like the result converges around $0.660162$: Table[N[Product[(Prime[i] (Prime[i] - 2)...

10

You are right!! Reverse /@ Table[IntegerDigits[Prime[i]], {i, 549, 2, -1}] // Flatten // FromDigits // PrimeQ True 7693749334931393929332939193719311937093988318837783368335831583748333\ 8332831283308379733973977396737673167393733373727391739073107379631963\ 7763376317639563346373631363326371633163706339533853185317539553755374\ ...

9

Minimization can be expressed with plain NMinimize in a bit awkward manner: NextHighlyCompositeNumber[n_Integer?Positive, primes:{__Integer?PrimeQ}] := With[{parms = Unique[] & /@ primes}, With[{eqn = Inner[Power, primes, parms, Times]}, Floor@First@NMinimize[{eqn, eqn >= n && parms \[Element] Integers && And @@ (...

9

The best analytic built-in approximation is the Riemann Prime Counting Function; it is implemented in Mathematica as RiemannR. So far we know exact values of $\pi$ prime counting function for n < 10^25, however in Mathematica its counterpart PrimePi[n] can be computed exactly to much lower values i.e. up to 25 10^13 -1, see e.g. What is so special about ...

9

I think this is what you are after: mySum[s_, a_, b_]:= Sum[ 1./n p^(-n s), {n, b}, {p, Prime @ Range @ PrimePi @ a}] Edit: skipper inner Sum, thanks to kguler's comment.

9

General There are as many solutions as prime numbers If you Solve for $x$ Solve[32 x + 1 == p, x] 1/32 (-1 + p) For every prime $p$ there will be an $x = \frac{p-1}{32}$ that satisfies. For any rational $x$ To see the firsts values you can use ReplaceAll on p with the first 100 Prime numbers, to get the first 100 values of $x$ that fulfill the ...

9

One convention (the usual?) for counting twin primes is to count just 1 for each pair. The original question is ambiguous, but it seems that @rhermans (+1) has a different convention of counting 2 for each pair. The following definition returns the lesser of all twin prime pairs $\{p,p+2\}$ such that $p \le x$. Make a list of primes up to $x$, then test for ...

8

By using a pregenerated list of prime numbers: lst = Prime[Range@PrimePi[25]]; Select[Union@Flatten[lst*# & /@ lst], # < 50 &] (* {4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49} *)

8

Try to use lowercase names at least for the initial letter of your functions. My timings are different than yours. Probably your computer is much faster than mine. In your code pro is calculated in 144 seconds and GCD[func[160001],pro] needs another 34 seconds so a total of 178 seconds. Of course pro is calculated only once but the same happens in the ...

Only top voted, non community-wiki answers of a minimum length are eligible