Faits:
Faits:
A. C._, né en 1956, a travaillé en qualité de maçon jusqu'au 18 mai 1998, date à laquelle il a cessé définitivement son activité lucrative en raison d'une atteinte à la santé. Le 14 juillet 1998, il a présenté une demande tendant à l'octroi de prestations de l'assurance-invalidité sous la forme d'une mesure de reclassement dans une nouvelle profession.
L'Office de l'assurance-invalidité pour le canton de Vaud a requis l'avis du docteur M._, médecin traitant de l'assuré (rapport du 4 septembre 1998) et soumis l'assuré à un examen médical qui a été confié au Service médical régional de l'assurance-invalidité (SMR), (rapport du 19 septembre 2001). En outre, l'administration a mis en oeuvre un stage d'évaluation au Centre d'observation professionnelle de l'assurance-invalidité (COP), (du 14 février au 10 mars 2000), ainsi qu'un stage d'intégration professionnelle au Centre de formation professionnelle (ORIPH), (du 4 septembre au 12 novembre 2000).
Par décision du 4 octobre 2001, l'office AI a rejeté la demande dont il était saisi, motif pris que le taux d'invalidité constatée (32 %) était insuffisant pour ouvrir droit à prestations.
Par décision du 4 octobre 2001, l'office AI a rejeté la demande dont il était saisi, motif pris que le taux d'invalidité constatée (32 %) était insuffisant pour ouvrir droit à prestations.
B. C._ a recouru contre cette décision devant le Tribunal des assurances du canton de Vaud, en concluant à l'octroi d'une demi-rente d'invalidité et à la mise en oeuvre de mesures d'ordre professionnel.
La juridiction cantonale a confié une expertise au docteur Z._, spécialiste en psychiatrie et psychothérapie (rapport du 7 juillet 2003), lequel a recueilli l'avis du docteur A._, spécialiste en psychiatrie et psychothérapie, et médecin traitant de l'assuré (rapport du 30 janvier 2003).
Par jugement du 18 décembre 2003, la juridiction cantonale a « réformé » la décision attaquée, en ce sens que l'assuré a droit à une demi-rente d'invalidité depuis le 1er août 1998.
Par jugement du 18 décembre 2003, la juridiction cantonale a « réformé » la décision attaquée, en ce sens que l'assuré a droit à une demi-rente d'invalidité depuis le 1er août 1998.
C. L'office AI interjette recours de droit administratif contre ce jugement, dont il demande l'annulation, en concluant à la confirmation de sa décision du 4 octobre 2001.
C._ conclut au rejet du recours. De son côté, l'Office fédéral des assurances sociales (OFAS) en propose l'admission.

Considérant en droit:
Considérant en droit:
1. 1.1 Le litige porte sur le droit éventuel de l'intimé à une rente d'invalidité.
1.2 La loi fédérale sur la partie générale du droit des assurances sociales du 6 octobre 2000 (LPGA) est entrée en vigueur le 1er janvier 2003, entraînant la modification de nombreuses dispositions légales dans le domaine de l'assurance-invalidité. Cependant, le cas d'espèce reste régi par les dispositions de la LAI en vigueur jusqu'au 31 décembre 2002, eu égard au principe selon lequel les règles applicables sont celles en vigueur au moment où les faits juridiquement déterminants se sont produits (<ref-ruling> consid. 1). En outre, le Tribunal fédéral des assurances apprécie la légalité des décisions attaquées, en règle générale, d'après l'état de fait existant au moment où la décision litigieuse a été rendue (<ref-ruling> consid. 1b).
Pour les mêmes motifs, les dispositions de la novelle du 21 mars 2003 modifiant la LAI (4ème révision), entrée en vigueur le 1er janvier 2004 (RO 2003 3852) ne sont pas non plus applicables.
Pour les mêmes motifs, les dispositions de la novelle du 21 mars 2003 modifiant la LAI (4ème révision), entrée en vigueur le 1er janvier 2004 (RO 2003 3852) ne sont pas non plus applicables.
2. 2.1 L'assuré a droit à une rente s'il est invalide à quarante pour cent au moins (<ref-law>). Pour l'évaluation de l'invalidité, le revenu du travail que l'invalide pourrait obtenir en exerçant l'activité qu'on peut raisonnablement attendre de lui, après exécution éventuelle de mesures de réadaptation et compte tenu d'une situation équilibrée du marché du travail, est comparé au revenu qu'il aurait pu obtenir s'il n'était pas invalide (<ref-law>).
2.2 L'office AI a refusé l'octroi d'une rente, motif pris que la comparaison des revenus déterminants permettait de fixer à 32 % le taux d'invalidité de l'assuré. Il a considéré que l'intéressé, malgré l'atteinte à sa santé, était en mesure d'exercer, sans limitation, une activité adaptée, tels des travaux de contrôle, d'opérateur sur machines, de montage industriel et de conditionnement. L'office AI s'est fondé pour cela sur l'appréciation des médecins du SMR, selon lesquels l'assuré souffre de lombalgies banales à l'origine d'un syndrome d'amplification des douleurs important, ainsi que d'un syndrome de conflit sous-acromial aux épaules. La pathologie lombaire ne faisait pas obstacle à l'exercice d'une activité permettant l'alternance de la position debout et de la position assise, permettant de brefs déplacements à pied régulièrement, n'imposant pas de travail prolongé en antéflexion ou latéroflexion du tronc, n'obligeant pas l'intéressé à soulever de manière régulière des charges d'un poids excédant 5 kilos ni à porter de manière régulière des charges d'un poids excédant 10 kilos. Quant à l'affection des épaules, elle n'empêche pas l'assuré d'accomplir un travail léger se faisant à la hauteur d'un établi et imposant uniquement le maniement d'objets légers (rapport du 19 septembre 2001). En revanche, l'office AI a refusé de tenir compte des incidences de troubles psychiatriques éventuels sur la capacité de travail et de gain, motif pris que de tels troubles n'ont pas été constatés ni même suspectés par les médecins du SMR.
De son côté, la juridiction cantonale a fixé à 50 % le taux de l'incapacité de travail dans une activité adaptée, compatible avec les différentes atteintes à la santé physique. Elle s'est référée pour cela à l'avis du docteur Z._ (rapport d'expertise judiciaire du 7 juillet 2003), lequel avait attesté un syndrome douloureux somatoforme persistant, ainsi qu'un trouble anxieux et dépressif mixte, et fait état d'une diminution de la capacité de travail de 50 %. Selon les premiers juges, s'il ne fait aucun doute que les troubles physiques dont souffre l'assuré ne sont pas négligeables, force est d'admettre que l'affection psychique est aussi présente; certes, le syndrome douloureux somatoforme persistant n'a pas le caractère de maladie invalidante au sens de la jurisprudence, mais le trouble anxieux et dépressif mixte est réel et doit être qualifié d'invalidant.
Dans son recours de droit administratif, l'office AI conteste ce point de vue en se référant à un avis du SMR (du 14 juin 2004), selon lequel le prononcé attaqué est peu étayé et, partant, peu convaincant. En particulier, les premiers juges ne disent pas pourquoi le trouble anxieux et dépressif mixte doit être qualifié d'invalidant. En outre, l'administration reproche à la juridiction cantonale de s'être fondée seulement sur des conjectures des experts en réadaptation professionnelle ou de l'expert judiciaire, selon lesquels « il est douteux que l'intéressé puisse reprendre une activité professionnelle, même à 50 % » ou « il semble raisonnable d'admettre une diminution de 50 % de la capacité de travail ».
Dans ses déterminations sur le recours de droit administratif, l'OFAS est d'avis que le rapport d'expertise du docteur Z._ n'a pas valeur probante. D'une part, l'expert n'indique pas si et dans quelle mesure l'assuré dispose des ressources psychiques qui lui permettraient de surmonter ses douleurs. D'autre part, le trouble somatoforme douloureux, apparu dès la fin des années 90 sous la forme d'une amplification des douleurs, ne saurait être qualifié d'affection invalidante, puisque le trouble anxieux et dépressif mixte, valant comme comorbidité psychiatrique, n'est apparu qu'au mois de septembre ou octobre 2002, en réaction aux douleurs et au refus de prestations de l'assurance-invalidité.
Dans ses déterminations sur le recours de droit administratif, l'OFAS est d'avis que le rapport d'expertise du docteur Z._ n'a pas valeur probante. D'une part, l'expert n'indique pas si et dans quelle mesure l'assuré dispose des ressources psychiques qui lui permettraient de surmonter ses douleurs. D'autre part, le trouble somatoforme douloureux, apparu dès la fin des années 90 sous la forme d'une amplification des douleurs, ne saurait être qualifié d'affection invalidante, puisque le trouble anxieux et dépressif mixte, valant comme comorbidité psychiatrique, n'est apparu qu'au mois de septembre ou octobre 2002, en réaction aux douleurs et au refus de prestations de l'assurance-invalidité.
3. 3.1 Sur le plan somatique, il n'y a pas de raison de mettre en doute les conclusions des médecins du SMR, selon lesquelles les troubles lombaires et l'affection des épaules n'empêchent pas l'assuré d'exercer une activité légère sans port de charges et permettant l'alternance des positions. En effet, ces médecins ont attesté l'existence de troubles banals de la statique rachidienne, marqués au niveau lombaire par une amplification importante des douleurs, sans fondement organique avéré. En ce qui concerne les épaules, les médecins du SMR ont souligné l'absence d'amélioration malgré les opérations réalisées (réparation de la coiffe des rotateurs, acromioplastie au niveau des deux épaules), un status marqué par des signes de non utilisation ou de sous-utilisation tout à fait nets. L'appréciation des médecins du SMR n'est pas contredite par les autres médecins qui se sont prononcés sur le cas. En particulier, le docteur M._ a indiqué qu'une activité ne nécessitant pas le port de charges apparaissait adaptée. De son côté, le docteur E._, rhumatologue, dont l'avis a été produit par l'assuré en instance cantonale, a également relevé le caractère commun des lombalgies, ainsi que d'évidents phénomènes de sous-utilisation de la fonction des épaules. Selon ce médecin, la problématique est essentiellement de nature somatoforme (rapport du 5 septembre 2002).
3. 3.1 Sur le plan somatique, il n'y a pas de raison de mettre en doute les conclusions des médecins du SMR, selon lesquelles les troubles lombaires et l'affection des épaules n'empêchent pas l'assuré d'exercer une activité légère sans port de charges et permettant l'alternance des positions. En effet, ces médecins ont attesté l'existence de troubles banals de la statique rachidienne, marqués au niveau lombaire par une amplification importante des douleurs, sans fondement organique avéré. En ce qui concerne les épaules, les médecins du SMR ont souligné l'absence d'amélioration malgré les opérations réalisées (réparation de la coiffe des rotateurs, acromioplastie au niveau des deux épaules), un status marqué par des signes de non utilisation ou de sous-utilisation tout à fait nets. L'appréciation des médecins du SMR n'est pas contredite par les autres médecins qui se sont prononcés sur le cas. En particulier, le docteur M._ a indiqué qu'une activité ne nécessitant pas le port de charges apparaissait adaptée. De son côté, le docteur E._, rhumatologue, dont l'avis a été produit par l'assuré en instance cantonale, a également relevé le caractère commun des lombalgies, ainsi que d'évidents phénomènes de sous-utilisation de la fonction des épaules. Selon ce médecin, la problématique est essentiellement de nature somatoforme (rapport du 5 septembre 2002).
3.2 3.2.1 Les atteintes à la santé psychique peuvent, comme les atteintes physiques, entraîner une invalidité au sens de l'<ref-law>. On ne considère pas comme des conséquences d'un état psychique maladif, donc pas comme des affections à prendre en charge par l'assurance-invalidité, les diminutions de la capacité de gain que l'assuré pourrait empêcher en faisant preuve de bonne volonté; la mesure de ce qui est exigible doit être déterminée aussi objectivement que possible (<ref-ruling>; VSI 2001 p. 224 consid. 2b et les références; cf. aussi <ref-ruling> consid. 4c in fine).
La reconnaissance de l'existence d'une atteinte à la santé psychique, soit aussi de troubles somatoformes douloureux persistants, suppose d'abord la présence d'un diagnostic émanant d'un expert (psychiatre) et s'appuyant lege artis sur les critères d'un système de classification reconnu (<ref-ruling> ss consid. 5.3 et consid. 6). Comme pour toutes les autres atteintes à la santé psychique, le diagnostic de troubles somatoformes douloureux persistants ne constitue pas encore une base suffisante pour conclure à une invalidité. Au contraire, il existe une présomption que les troubles somatoformes douloureux ou leurs effets peuvent être surmontés par un effort de volonté raisonnablement exigible. Le caractère non exigible de la réintégration dans le processus de travail peut résulter de facteurs déterminés qui, par leur intensité et leur constance, rendent la personne incapable de fournir cet effort de volonté. Dans un tel cas, en effet, l'assuré ne dispose pas des ressources nécessaires pour vaincre ses douleurs. La question de savoir si ces circonstances exceptionnelles sont réunies doit être tranchée de cas en cas à la lumière de différents critères. Au premier plan figure la présence d'une comorbidité psychiatrique importante par sa gravité, son acuité et sa durée. D'autres critères peuvent être déterminants. Ce sera le cas des affections corporelles chroniques, d'un processus maladif s'étendant sur plusieurs années sans rémission durable (symptomatologie inchangée ou progressive), d'une perte d'intégration sociale dans toutes les manifestations de la vie, d'un état psychique cristallisé, sans évolution possible au plan thérapeutique, résultant d'un processus défectueux de résolution du conflit, mais apportant un soulagement du point de vue psychique (profit primaire tiré de la maladie, fuite dans la maladie), de l'échec de traitements ambulatoires ou stationnaires conformes aux règles de l'art (même avec différents types de traitement), cela en dépit de l'attitude coopérative de la personne assurée (<ref-ruling>). Plus ces critères se manifestent et imprègnent les constatations médicales, moins on admettra l'exigibilité d'un effort de volonté (Meyer-Blaser, Der Rechtsbegriff der Arbeitsunfähigkeit und seine Bedeutung in der Sozialversicherung, in: Schmerz und Arbeitsunfähigkeit, St. Gall 2003, p. 77).
Si les limitations liées à l'exercice d'une activité résultent d'une exagération des symptômes ou d'une constellation semblable, on conclura, en règle ordinaire, à l'absence d'une atteinte à la santé ouvrant le droit à des prestations d'assurance. Au nombre des situations envisagées figurent la discordance entre les douleurs décrites et le comportement observé, l'allégation d'intenses douleurs dont les caractéristiques demeurent vagues, l'absence de demande de soins, les grandes divergences entre les informations fournies par le patient et celles ressortant de l'anamnèse, le fait que des plaintes très démonstratives laissent insensible l'expert, ainsi que l'allégation de lourds handicaps malgré un environnement psychosocial intact (voir Kopp/Willi/Klipstein, Im Graubereich zwischen Körper, Psyche und sozialen Schwierigkeiten, in: Schweizerische Medizinische Wochenschrift 1997, p. 1434, avec référence à une étude approfondie de Winckler et Foerster; voir sur l'ensemble du sujet consid. 1.2. destiné à la publication de l'arrêt J. du 16 décembre 2004, I 770/03).
3.2.2 En l'espèce, le docteur Z._ a fait état d'une comorbidité psychiatrique sous la forme d'un trouble anxieux et dépressif mixte, d'intensité légère à modérée. Selon l'expert, ce trouble n'est apparu qu'en 2002, en réaction aux douleurs et au refus de prestations de l'assurance-invalidité. On doit dès lors nier l'existence, dans le cas particulier, d'une comorbidité psychiatrique importante par sa gravité, son acuité et sa durée. Certes, dans un rapport du 7 octobre 2003, le docteur B._, chef de clinique au Département universitaire de psychiatrie adulte (DUPA), a fait état de la survenance, au mois de septembre 2003, d'une péjoration de l'état de santé sous la forme d'un trouble dépressif récurrent, épisode actuel sévère. Toutefois, du moment que le Tribunal fédéral des assurances apprécie la légalité des décisions attaquées, en règle générale, d'après l'état de fait existant au moment où la décision litigieuse a été rendue (cf. consid. 1.2), il n'y a pas lieu de tenir compte d'une modification de l'état de santé survenue après le 4 octobre 2001.
En l'absence d'une comorbidité psychiatrique importante, il convient d'examiner si sont réunis en l'occurrence les autres critères mentionnés par la jurisprudence pour fonder le caractère non exigible de la réintégration dans le processus de travail ou si, au contraire, les limitations liées à l'exercice d'une activité résultent d'une exagération des symptômes ou d'une constellation semblable (cf. consid. 3.2.1).
Le docteur Z._ a nié l'existence d'une perte d'intégration sociale dans toutes les manifestations de la vie car, même s'il a perdu son emploi et une partie des relations sociales qui lui étaient liées, l'assuré reste cependant intégré dans son milieu familial et garde des amis. En ce qui concerne un éventuel profit tiré de la maladie, l'expert a énuméré les prestations des assurances sociales et l'assistance des services sociaux obtenues au titre de compensation financière de sa maladie. Si l'on tient compte, en outre, du fait que le trouble psychique est apparu en réaction au refus de prestations de l'assurance-invalidité, on ne peut nier l'existence d'un certain profit tiré de la maladie. Au sujet de l'efficacité des soins dont a bénéficié l'intéressé, le docteur Z._ a indiqué que celui-ci avait suivi les traitements rendus nécessaires par les atteintes somatiques. Toutefois, selon ce médecin, l'observation du traitement antidépresseur est manifestement médiocre. Sur le vu de ces constatations médicales, il apparaît que les critères mentionnés par la jurisprudence pour fonder le caractère non exigible de la réintégration dans le processus de travail ne se manifestent pas dans une mesure telle qu'il faille nier l'exigibilité d'un effort de volonté.
Au demeurant, étant donné les facteurs mis en évidence par l'expert, force est de considérer que les limitations liées à l'exercice d'une activité résultent en partie d'une exagération des symptômes. Ainsi, bien qu'il ait nié l'existence d'une discordance entre les douleurs décrites et le comportement observé, le docteur Z._ a souligné l'allégation d'intenses douleurs dont les caractéristiques demeurent vagues, puisqu'elles « sont tellement généralisées qu'il est difficile d'en obtenir une description précise et spécifique ». En outre, bien que l'expert ait répondu négativement à la question de savoir s'il y avait une absence de demande de soins, cette constatation doit être relativisée au regard de l'observance manifestement médiocre du traitement antidépresseur. Enfin, le docteur Z._ a indiqué que l'assuré faisait état de lourds handicaps (douleurs à la colonne, au bas du dos jusque dans le bassin, aux épaules, aux genoux, dans les mains; impossibilité de porter une charge de 50 gr.; douleurs augmentées par l'effort, mais également par l'inactivité; fatigue permanente; vertiges), tout en relevant que l'intéressé conserve par exemple la capacité de se rendre seul en voiture de X._ à Y._, plusieurs fois par semaine, pour suivre son traitement.
Vu ce qui précède, il y a lieu de présumer que les troubles somatoformes douloureux ou leurs effets peuvent être surmontés par un effort de volonté raisonnablement exigible, ce que les premiers juges ont d'ailleurs admis implicitement en déniant à ces troubles le caractère de maladie invalidante au sens de la jurisprudence.
En revanche, il convient de s'écarter du point de vue de la juridiction cantonale lorsqu'elle reconnaît un tel caractère au trouble anxieux et dépressif mixte. Il ressort en effet du rapport de l'expert judiciaire que ce trouble, d'intensité légère à modérée, n'est pas invalidant.
Cela étant, l'existence d'une atteinte psychique ouvrant le droit à des prestations d'assurance doit être niée. L'office recourant était dès lors fondé à considérer que la capacité de travail découlant de l'atteinte à la santé était entière dans une activité adaptée du genre de celles qui ont été préconisées par les médecins du SMR dans leur rapport du 19 septembre 2001.
Cela étant, l'existence d'une atteinte psychique ouvrant le droit à des prestations d'assurance doit être niée. L'office recourant était dès lors fondé à considérer que la capacité de travail découlant de l'atteinte à la santé était entière dans une activité adaptée du genre de celles qui ont été préconisées par les médecins du SMR dans leur rapport du 19 septembre 2001.
4. Le salaire auquel peuvent prétendre les hommes effectuant des activités simples et répétitives dans le secteur privé s'élevait, en 1998, à 4'268 fr. mensuellement, part au 13ème salaire comprise (Enquête suisse sur la structure des salaires 1998, TA 1; niveau de qualification 4), soit 51'216 fr. annuellement. Comme l'année déterminante en l'occurrence (cf. <ref-ruling>, 128 V 174) est 1999, ce montant doit être adapté, ce qui donne un gain annuel de 51'370 fr. (51'216 x 100,3 %). Etant donné que les salaires bruts standardisés sont fondés sur un horaire de travail de 40 heures, soit une durée hebdomadaire inférieure à la moyenne usuelle dans les entreprises en 1999 (41,8 heures; La Vie économique 4-2004 p. 86, tableau B 9.2), ce montant doit être porté à 53'681 fr. Par ailleurs, le revenu sans invalidité doit être fixé à 60'536 fr. selon l'attestation de l'employeur pour l'année 1998 et moyennant une adaptation des prix à l'année 1999 (4'680 x 13 x [100 % - 0,5 %]). Cela étant, même en admettant un taux de déduction maximum de 25 % sur le salaire tiré de statistiques (cf. <ref-ruling>), le taux d'invalidité (arrondi : cf. <ref-ruling>) doit être fixé à 33 % - (60'536 - [75 % x 53'681]) x 100 : 60'536 = 33,49 % -, taux insuffisant pour ouvrir droit à une rente.
L'office recourant était dès lors fondé, par sa décision du 4 octobre 2001, à nier le droit de l'intimé à une telle prestation et le recours se révèle bien fondé.
L'office recourant était dès lors fondé, par sa décision du 4 octobre 2001, à nier le droit de l'intimé à une telle prestation et le recours se révèle bien fondé.
5. Dans sa demande de prestations du 14 juillet 1998, l'assuré a requis l'octroi de prestations de l'assurance-invalidité sous la forme d'une mesure de reclassement dans une nouvelle profession. L'office AI a rejeté, sans autres précisions, la demande de prestations, motif pris que le taux d'invalidité n'était que de 32 %. De son côté, la juridiction cantonale ne s'est pas prononcée sur la conclusion de l'intéressé tendant à la mise en oeuvre de mesures d'ordre professionnel. Comme une diminution de la capacité de gain de 20 % environ est suffisante pour ouvrir droit à une mesure de reclassement (<ref-ruling> consid. 2b; VSI 2000 p. 63), il convient de renvoyer le dossier à l'office recourant pour qu'il examine si les autres conditions d'octroi d'une telle prestation sont réalisées.

Par ces motifs, le Tribunal fédéral des assurances prononce:
Par ces motifs, le Tribunal fédéral des assurances prononce:
1. Le recours est admis et le jugement du Tribunal des assurances du canton de Vaud du 18 décembre 2003 est annulé.
1. Le recours est admis et le jugement du Tribunal des assurances du canton de Vaud du 18 décembre 2003 est annulé.
2. Le dossier est renvoyé à l'Office de l'assurance-invalidité pour le canton de Vaud, afin qu'il statue sur le droit éventuel de l'intimé à une mesure de reclassement.
2. Le dossier est renvoyé à l'Office de l'assurance-invalidité pour le canton de Vaud, afin qu'il statue sur le droit éventuel de l'intimé à une mesure de reclassement.
3. Il n'est pas perçu de frais de justice.
3. Il n'est pas perçu de frais de justice.
4. Le présent arrêt sera communiqué aux parties, au Tribunal des assurances du canton de Vaud et à l'Office fédéral des assurances sociales.
Lucerne, le 12 mai 2005
Au nom du Tribunal fédéral des assurances
Le Président de la IIe Chambre: Le Greffier: