Headlights turn off randomly

once I changed the bulbs, the problem went away

you can buy them on Amazon a lot cheaper than Toyota

 

You don't say if you have the 2004 with halogen or with HID bulbs. If you have the HID bulbs, that means the bulbs need to be replaced.

Read this: Not all HID Bulbs are created equal | PriusChat

Especially the part that says:

 

My headlight would shut off on the passenger side and sometimes both lights would go out turning the switch on and off would make them come back on this attracts attention and works good if you want to get pulled over and harassed.
I purchased an HID kit from ebay for $39.00, on the bottom of the headlight assembly on each side is an aluminum cover that contains the power supply. The bulbs had a plastic base that had to be carved down to size to fit the prius. The ebay add claimed it fit the prius it didn't fit out of the box. Be careful when grinding the base to hold the wires out of the way and don't grind your fingers which goes without saying. There is a black and red wire that has wide spade terminals they are too wide to fit the connector that plugs into the prius power supply and leads to the headlight bulb access cap. The Spade terminals could be cut off and smaller ones crimped on I ground them down and shortened them with a grinder. The plastic cap that covers the opening to access the bulbs has an arrow that lines up with a a vertical line on the housing the wider line is where it opens, it is difficult to rotate. Once the arrow and the mark are lined up pry it off with a screw driver.
The compartment where the power supply is located has a triangular plastic sheet that has to be cut out to insert the new power supply which can be attached with the provided double sided tape to the bottom of the cavity, the original power source was attached to the aluminum cover with screws. Four screws attach the headlight assembly to the car body. There is one bolt behind the inner fender that attaches the bumper cover to the fender, 2 plastic fasteners under the hood that attaches the bumper cover to the radiator support, and two screws with rubber bumpers that the hood rests on when closed. Pull the bumper cover away from the fender it will expose a black plastic part attached to the fender with screws in it, these screws are not necessary to remove the bolts you need to remove are below in the metal the other two headlight bolts are easy to find.
Best of luck if you try this fix it worked for me and I like the bright white headlights my old ones were yellow.