You need some kind of organizational structure where the sprites are placed in. For example, you could keep all sprites in a hash table where the hash is based on the world-location so each "world zone" has its own bucket in the hash table. Then you could rapidly access only sprites near the one you are testing.
You can also look up "quad-tree," which is another (slightly more complicated) standard solution for this problem.
If you don't want to do either of those, you could just test if each sprite is within a certain maximum sprite size distance from the colliding sprite before doing a full collision detection. (Don't use the "distance formula" here. sqrt is slow.) This might help, but is still not very scalable since even those tests on enough sprites will bog down your frame rate.
Edit: In general this is referred to as "broad-phase," "mid-phase," and "narrow phase" collision detection. Broad-phase uses a quad tree, hash table, or similar to see if the object is even in the "ball park." Mid-phase tests if the "bounding boxes" (the smallest 2D or 3D, non-rotated box shape that encompasses the object) overlap. Narrow-phase is the actual collision detection that takes into account rotation, odd shapes, or whatever else you need.
Any serious and fast collision detection will use (at least) those 3 phases. The second paragraph solution I gave basically skips the broad-phase test. It's also possible you're not concerned with narrow-phase tests if you only care if the sprite's bounding boxes are intersecting and not the actual displayed shapes.
