Faits: Faits: A. A._, B._, C._, D._, E._, F._, G._, H._, I._, J._, K._, L._, M._, N._, O._, P._, sont tous titulaires d'un diplôme d'ingénieur HES délivré sur la base des dispositions transitoires prévues par l'art. 26 al. 1 de l'ordonnance du 11 septembre 1996 relative à la création et à la gestion des hautes écoles spécialisées (ordonnance sur les hautes écoles spécialisées; OHES; RS 414.711) et par l'ordonnance du Département fédéral de l'économie du 4 juillet 2000 sur l'obtention a posteriori du titre d'une haute école spécialisée (RS 414.711.5). Ils font partie du corps enseignant des écoles professionnelles du canton du Valais et leur statut est régi par l'ordonnance valaisanne du 21 août 1991 concernant le statut et le traitement du personnel de l'enseignement professionnel (ci-après: OPEP/VS). L'art. 10 OPEP/VS, qui répartit les maîtres de l'enseignement professionnel en cinq classes, définit comme suit les quatrième et cinquième classes: "La quatrième classe comprend: 1. les porteurs du diplôme fédéral de maître professionnel pour l'enseignement des branches de culture générale; 2. les porteurs du diplôme fédéral de maître professionnel pour l'enseignement des branches techniques; 3. les porteurs du diplôme de maître de l'enseignement secondaire du premier degré; 4. les porteurs du diplôme fédéral de maîtrise; 5. les ingénieurs ETS (article 59 de la loi fédérale sur la formation professionnelle); 6. sur proposition de l'inspecteur de l'enseignement professionnel et de l'apprentissage et du directeur de l'école professionnelle, les maîtres des deuxième et troisième classes qui ont dix ans d'activité à l'école professionnelle, qui ont suivi les cours de perfectionnement exigés par la direction de l'école et qui donnent satisfaction. La cinquième classe comprend: 1. les porteurs d'un grade universitaire (licence ou doctorat) ou d'un diplôme de l'enseignement secondaire du deuxième degré; 2. les ingénieurs et les architectes diplômés des écoles polytechniques fédérales." Le 20 août 2003, les intéressés ont présenté au Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) une requête en changement de classe dans le sens d'une promotion de la quatrième à la cinquième classe, incluant une augmentation de leur traitement. Invoquant l'art. 2 de la loi fédérale du 6 octobre 1995 sur les hautes écoles spécialisées (LHES; RS 414.71), ils ont fait valoir que leur titre d'ingénieur HES devait être assimilé à un diplôme universitaire. Se fondant sur le préavis négatif de la Commission valaisanne de classification du personnel enseignant, le Conseil d'Etat a rejeté la requête de A._ et consorts, par décision du 18 février 2004. Se fondant sur le préavis négatif de la Commission valaisanne de classification du personnel enseignant, le Conseil d'Etat a rejeté la requête de A._ et consorts, par décision du 18 février 2004. B. Saisie d'un recours dirigé contre la décision du Conseil d'Etat du 18 février 2004, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) l'a rejeté, par arrêt du 12 juillet 2004. Le Tribunal cantonal a notamment retenu que l'art. 2 LHES n'imposait pas aux cantons de rémunérer de façon identique les porteurs de diplômes universitaires et les détenteurs de diplômes HES, que l'argument tiré d'une prétendue violation du principe de la force dérogatoire du droit fédéral n'était pas fondé et que la distinction opérée par l'art. 10 OPEP/VS ne heurtait pas le principe constitutionnel de l'égalité de traitement. B. Saisie d'un recours dirigé contre la décision du Conseil d'Etat du 18 février 2004, la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) l'a rejeté, par arrêt du 12 juillet 2004. Le Tribunal cantonal a notamment retenu que l'art. 2 LHES n'imposait pas aux cantons de rémunérer de façon identique les porteurs de diplômes universitaires et les détenteurs de diplômes HES, que l'argument tiré d'une prétendue violation du principe de la force dérogatoire du droit fédéral n'était pas fondé et que la distinction opérée par l'art. 10 OPEP/VS ne heurtait pas le principe constitutionnel de l'égalité de traitement. C. Agissant par la voie du recours de droit public, A._ et quinze consorts, à savoir B._, C._, D._, E._, F._, G._, H._, I._, J._, K._, L._, M._, N._, O._, P._, demandent au Tribunal fédéral, avec suite de frais et dépens, d'annuler l'arrêt du Tribunal cantonal du 12 juillet 2004 et de renvoyer le dossier à cette autorité "pour nouveau jugement dans le sens des considérants". Ils font essentiellement valoir la violation du principe de la primauté et du respect du droit fédéral (art. 49 Cst.) ainsi que celle du principe de l'égalité (art. 8 Cst.). Ils requièrent la production d'un dossier. Le Tribunal cantonal a expressément renoncé à se déterminer sur le recours. Le Conseil d'Etat conclut au rejet du recours, sous suite de frais. 