Intervals, the circle of 5ths, both have worked about as well for me. For major scales (clarinet playing) I just memorized the notes because you play the so very much. Every day. I found that after I had the majors down well, I could make the changes to get the other scale forms - natural minor, harmonic minor, melody minor... and other modes. Everything I do is based with that major scale as the foundation.
Here's something crazy - I can play intervals WWHWWWH more easily with a trumpet or euphonium but not any of the woodwind instruments. Something about those three valves makes quicker sense of it in my brain.
Here are some interval formulas for different scales/modes:
Major Scale: R, W, W, H, W, W, W, H
Natural Minor Scale: R, W, H, W, W, H, W, W
Harmonic Minor Scale: R, W, H, W, W, H, 1 1/2, H (notice the step and a half)
Melodic Minor Scale: going up is: R, W, H, W, W, W, W, H
going down is: R, W, W, H, W, W, H, W
Dorian Mode is: R, W, H, W, W, W, H, W
Mixolydian Mode is: R, W, W, H, W, W, H, W
Ahava Raba Mode is: R, H, 1 1/2, H, W, H, W, W
A minor pentatonic blues scale (no sharped 5) is: R, 1 1/2, W, W, 1 1/2, W
The R refers to the root, or first note of the scale.