prime_range should allow a step

sagemath / sage

Main repository of SageMath

https://www.sagemath.org

Other

1.31k stars 450 forks source link

prime_range should allow a step #29760

Open kedlaya opened 4 years ago

kedlaya commented 4 years ago

Is there any reason not to implement the following?

sage: prime_range(11, 100, 10)
[11, 31, 61, 71]

For this ticket, I have in mind the easy fix of running the same internal algorithm and retaining only the answers in the desired congruence class; that is, prime_range(x, y, z) would be equivalent to

[p for p in prime_range(x, y) if (p-x)%z == 0]

A more advanced (and more efficient) version would be to change the underlying algorithm.

Depends on #31548

CC: @DaveWitteMorris

Component: number theory

Author: David Roe

Branch/Commit: u/roed/prime_range @ 7f0a385

Issue created by migration from https://trac.sagemath.org/ticket/29760

kedlaya commented 3 years ago

Description changed:

--- 
+++ 
@@ -7,6 +7,6 @@
 For this ticket, I have in mind the easy fix of running the same internal algorithm and retaining only the answers in the desired congruence class; that is, `prime_range(x, y, z)` would be equivalent to

-p for p in prime_range(x, y) if (p-x)%z == 0 +[p for p in prime_range(x, y) if (p-x)%z == 0]

 A more advanced (and more efficient) version would be to change the underlying algorithm.

kedlaya commented 3 years ago

comment:1

Upon further reflection, maybe I should also be asking for this in the primes iterator.

mkoeppe commented 3 years ago

comment:2

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.