Project Euler help

[gaunt gazelle]

⌛ This post has been reserved for your question.

Hey @quasi palm! Please use /close or the Close Post button above when you're finished. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

[chrome quest]

it seems like you are interested in all coprime numbers until a specific point

so you could try building a data structure essentially storing that information similar to a prime sieve

you could start with a 2D boolean array

so you'd have an entry for each combination of two numbers

[quasi palm]

Wouldn't the answer be just the highest numbers smaller than 1 million constructed from just prime numbers?

510510 probably

No

[chrome quest]

x23456789
2-c-c-c-c
3c-cc-cc-
4-c-c-c-c
5ccc-cccc
6---c-c--
7ccccc-cc
8-c-c-c-c
9c-cc-cc-

here's a simple example of what is coprime and what is not

there are a few patterns you can use for optimizing

(in the table, c means coprime and - neans not coprime)

I didn't even read the problem statement lol

viewing websites with problem statements is typically annoying on mobile

[chrome quest]

what I would have told you is that

• this table is mirrored by the diagonal so you'd just have to compute the diagonal
• you can easily compute which are comprime and which aren't for prime numbers
• for multiple of composed numbers, a number is only coprime if it is coprime with all factors (you just need to have it as a multiple of two numbers (i.e. you need one prime factor which you can find with a prime sieve) and then quickly compute it

With that, you could get your code to a complexity of O(n^2) without reasoning about that totient thing

[quasi palm]

O(n^2) with n=100000 would take a bit.

Fortunately Euler only requires an answet, but still.

[chrome quest]

idk that project euler thing

[quasi palm]

It's unique in that it doesn't require you to submit code. So you can brute-force answers on a server with bazillion cores if you want.

[chrome quest]

also an array that's between 1 and 2 GB in size lmao

ig that O(n^2) approach wouldn't even take that long if optimized well (including vectorization)