List of Primes for generic type

I'm writing a prime number checker that works on types with trait FromPrimitive (which is part of my Numeric trait):

fn is_prime<T: Numeric>(n: T) -> bool

There are a few tests to check this but the first is a simple check to see if it's divisible by any prime less than 1000 to which end, I've got a static array of i32 which contains all 168 such primes. The easiest way to do this is just to pull these i32s out and run T::from_i32(p) on each of them, but can be a rather involved conversion and this prime checker can potentially be called LOTS so I want this to be more efficient. In particular, ideally I'd like to have is_prime create an array of T type primes if it hasn't already been created and pull it's values from that so that this conversion is only done once and not every time you call is_prime(). At first I thought I'd create a TypeMap variable as a lazy_static and then use that to reference for T, creating a new entry if one didn't exist. The problem is that it has to be mutable so I can add the array later and lazy_static doesn't like mutable things. So the question is:

How best to go about doing such a thing?

You could use interior mutability by wrapping the HashMap inside a Mutex. Here a basic example (using once_cell::sync::Lazy instead of lazy_static).

3 Likes

An alternate approach would be to do the conversion the other way: Attempt to convert n to u16, and then check against your list if the conversion is successful. If it's not, then you know that you're checking a (moderately) large number.

3 Likes

I haven't gotten it to work perfectly yet for my case but I think this is the right direction. Thanks very much!

Better yet, if it needs to be mutable, don't make it a global at all. All this patterns end up being more cleanly realized with a clean, mutable "Context" object that wraps all state needed for the calculation, and on which you can call the appropriate methods after being initialized in a local variable.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.