# Number of primes p less than or equal to X satisfying a congruence relation

I'm looking for a code that finds the number of primes p less than or equal to X satisfying p is congruent to 1 (mod 4) and another code that finds the number of primes p less than or equal to X satisfying p is congruent to 3 (mod 4).

Define a function that takes in a range and a criterion function.

fPrime[X_?NumericQ, f_Function] := {Length@#, #} &@
Table[If[f@Prime[i], Prime[i], Nothing], {i, PrimePi[X]}]


Usage

fPrime[100, Mod[#, 4] == 1 &]


{11, {5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97}}

fPrime[100, Mod[#, 4] == 3 &]


{13, {3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83}}

• I’m trying to find the number of primes in a large interval. It seems like what you’re providing is going to give me a set of primes and not the count. Oct 16, 2022 at 16:38
• It is providing you with both and you can choose to drop what you don't need.
– Syed
Oct 16, 2022 at 16:39
• Got it. Thanks! Oct 16, 2022 at 17:13
Select[Range,And[PrimeQ[#],Mod[#,4]==1]&]
(* {5,13,17,29,37,41,53,61,73,89,97} *)

Select[Range,And[PrimeQ[#],Mod[#,4]==3]&]
(* {3,7,11,19,23,31,43,47,59,67,71,79,83} *)

• One can observe that PrimePi4m1[x]+PrimePi4m3[x]+1==PrimePi[x]. This is the first step to make it more efficient. Another step would be harnessing PrimePi in a more extended way, something like it was done here. Oct 16, 2022 at 13:34
• Thank you. This code is really just a translation of an English sentence into Mathematica (more or less). There is certainly room for improvement if efficiency is a concern. Oct 16, 2022 at 13:59
• I’m not sure how to make this code work since it’s giving me the primes and not the number of primes. Oct 16, 2022 at 16:36
• You can apply Length to the result. Oct 16, 2022 at 16:43