Faits :
A.
A._, ressortissant algérien, né en 1974, a contracté mariage, le 1er octobre 2004 en Suisse avec B._, ressortissante suisse née en 1948.
Par requête du 28 septembre 2009, l'intéressé a demandé la naturalisation facilitée qu'il a obtenue le 3 août 2011 - décision entrée en force le 16 septembre 2011 - après avoir co-signé avec son épouse le 22 juillet 2011 une déclaration confirmant la stabilité et l'effectivité de leur communauté conjugale.
Les époux ont déposé le 7 janvier 2013 une requête commune en divorce. Celui-ci a été prononcé par jugement du 8 mars 2013. Le 2 mai 2013, A._ a épousé en Algérie C._, ressortissante algérienne née en 1986, laquelle a ensuite sollicité une autorisation de séjour en Suisse pour regroupement familial.
B.
Le 27 juin 2013, l'Office fédéral des migrations (ODM; Secrétariat d'Etat aux migrations depuis le 1 er janvier 2015) a informé l'intéressé qu'il devait examiner s'il y avait lieu d'annuler la décision d'octroi de la naturalisation facilitée, compte tenu de la brève période écoulée entre cette naturalisation, son divorce et son remariage avec une jeune compatriote. Dans ses observations du 4 juillet 2013, A._ a indiqué être prêt à répondre à toutes les questions relatives à son union avec son ex-épouse. Cette dernière a été auditionnée le 13 janvier 2014 en présence de l'intéressé. Elle a notamment expliqué avoir fait la connaissance de celui-ci en 2003 dans le cadre d'une communication via Internet et l'avoir ensuite fréquenté lors de vacances communes en Tunisie, avant de l'épouser. Elle a également précisé qu'elle était parfaitement consciente que leur relation s'arrêterait le jour où l'intéressé aurait envie de fonder une famille; elle savait ainsi dès le début qu'elle allait un jour céder sa place à une plus jeune femme. Elle a ajouté que leur communauté conjugale était encore stable et effective lors de la naturalisation de son ex-époux en août 2011, mais qu'au printemps 2012 celui-ci l'avait informée qu'il avait rencontré une jeune femme avec laquelle il pourrait fonder une famille; ils avaient alors commencé à envisager le divorce et s'étaient finalement séparés en septembre 2012.
Après avoir obtenu l'assentiment des autorités cantonales compétentes, l'ODM a, le 15 avril 2014, annulé la naturalisation facilitée accordée à A._.
C.
Le Tribunal administratif fédéral a confirmé cette décision dans un arrêt rendu le 19 mai 2015. Il a considéré que l'enchaînement chronologique des événements fondait la présomption que la communauté conjugale formée par les intéressés n'était pas stable au moment de la signature de la déclaration commune, respectivement lors du prononcé de la décision de naturalisation, et que les éléments avancés par A._ n'étaient pas susceptibles de renverser cette présomption.
D.
Par acte du 26 juin 2015, A._ forme un recours en matière de droit public à l'encontre de cet arrêt en concluant à son annulation et au maintien de la naturalisation facilitée qui lui a été accordée. Il sollicite également l'octroi de l'effet suspensif.
Invités à se déterminer, le Secrétariat d'Etat aux migrations a conclu au rejet du recours, tandis que l'autorité précédente a renoncé à formuler des observations.
Par ordonnance du 10 juillet 2015, le Juge présidant de la Ire Cour de droit public du Tribunal fédéral a accordé l'effet suspensif.

Considérant en droit :
1.
Dirigé contre la décision du Tribunal administratif fédéral qui confirme l'annulation de la naturalisation facilitée accordée au recourant, le recours est recevable comme recours en matière de droit public (art. 82 al. 1 let. a et 86 al. 1 let. a LTF). Le motif d'exclusion de l'<ref-law> n'entre pas en ligne de compte, dès lors qu'il s'agit en l'espèce de naturalisation facilitée et non pas de naturalisation ordinaire. Pour le surplus, le recourant a la qualité pour recourir au sens de l'<ref-law> et les conditions formelles de recevabilité sont remplies, de sorte qu'il y a lieu d'entrer en matière.
2.
Le recourant se plaint d'une mauvaise application de l'art. 41 al. 1 de la loi fédérale sur la nationalité du 29 septembre 1952 (LN; RS 141.0). Il reproche en substance à l'instance précédente d'avoir nié l'existence d'une communauté conjugale stable et effective lors de la signature de la déclaration de vie commune. L'appréciation de l'instance précédente reposerait à ses yeux sur une appréciation arbitraire des faits.
2.1. Conformément à l'art. 41 al. 1 LN, l'ODM peut, avec l'assentiment de l'autorité du canton d'origine, annuler la naturalisation ou la réintégration obtenue par des déclarations mensongères ou la dissimulation de faits essentiels.
2.1.1. Pour qu'une naturalisation facilitée soit annulée, il ne suffit pas qu'elle ait été accordée alors que l'une ou l'autre de ses conditions n'était pas remplie; il faut qu'elle ait été acquise grâce à un comportement déloyal et trompeur. S'il n'est point besoin que ce comportement soit constitutif d'une escroquerie au sens du droit pénal, il est nécessaire que l'intéressé ait donné sciemment de fausses informations à l'autorité ou qu'il l'ait délibérément laissée dans l'erreur sur des faits qu'il savait essentiels (<ref-ruling> consid. 2 p. 165; <ref-ruling> consid. 3.1 p. 115 et les arrêts cités). Tel est notamment le cas si le requérant déclare vivre en communauté stable avec son conjoint alors qu'il envisage de se séparer une fois obtenue la naturalisation facilitée; peu importe que son mariage se soit ou non déroulé jusqu'ici de manière harmonieuse (arrêts 1C_256/2012 du 22 novembre 2012 consid. 3.2.1; 1C_406/2009 du 28 octobre 2009 consid. 3.1.1 et l'arrêt cité).
La nature potestative de l'art. 41 al. 1 LN confère une certaine liberté d'appréciation à l'autorité compétente, qui doit toutefois s'abstenir de tout abus dans l'exercice de celle-ci. Commet un abus de son pouvoir d'appréciation l'autorité qui se fonde sur des critères inappropriés, ne tient pas compte de circonstances pertinentes ou rend une décision arbitraire, contraire au but de la loi ou au principe de la proportionnalité (<ref-ruling> consid. 3.1 p. 403; <ref-ruling> consid. 4a p. 101 et les arrêts cités).
D'après la jurisprudence, la notion de communauté conjugale suppose non seulement l'existence formelle d'un mariage, mais encore une véritable communauté de vie des conjoints; tel est le cas s'il existe une volonté commune et intacte de ceux-ci de maintenir une union conjugale stable; une séparation survenue peu après l'octroi de la naturalisation constitue un indice de l'absence de cette volonté lors de l'obtention de la citoyenneté suisse (<ref-ruling> consid. 2 p. 165; <ref-ruling> consid. 2 p. 484; <ref-ruling> consid. 3a p. 98).
2.1.2. La procédure administrative fédérale est régie par le principe de la libre appréciation des preuves (art. 40 de la loi fédérale de procédure civile fédérale du 4 décembre 1947 [PCF; RS 273], applicable par renvoi de l'<ref-law> [RS 172.021]). Ce principe vaut également devant le Tribunal administratif fédéral (<ref-law> [RS 173.32]). L'administration supporte le fardeau de la preuve lorsque la décision intervient, comme en l'espèce, au détriment de l'administré. Cela étant, la jurisprudence admet dans certaines circonstances que l'autorité puisse se fonder sur une présomption. C'est notamment le cas pour établir que le conjoint naturalisé a menti lorsqu'il a déclaré former une union stable, dans la mesure où il s'agit d'un fait psychique lié à des éléments relevant de la sphère intime, souvent inconnus de l'administration et difficiles à prouver (<ref-ruling> consid. 3 p. 166; <ref-ruling> consid. 3.2 p. 485). Partant, si l'enchaînement rapide des événements fonde la présomption de fait que la naturalisation a été obtenue frauduleusement, il incombe alors à l'administré de renverser cette présomption en raison, non seulement de son devoir de collaborer à l'établissement des faits (<ref-law>; cf. <ref-ruling> consid. 3 p. 166; <ref-ruling> consid. 3.2 p. 115 s.), mais encore de son propre intérêt (ATF <ref-ruling> consid. 3.2 p. 485 s.).
S'agissant d'une présomption de fait, qui ressortit à l'appréciation des preuves et ne modifie pas le fardeau de la preuve (cf. <ref-ruling> consid. 3 p. 166), l'administré n'a pas besoin, pour la renverser, de rapporter la preuve contraire du fait présumé, à savoir faire acquérir à l'autorité la certitude qu'il n'a pas menti; il suffit qu'il parvienne à faire admettre l'existence d'une possibilité raisonnable qu'il n'ait pas menti en déclarant former une communauté stable avec son conjoint. Il peut le faire en rendant vraisemblable, soit la survenance d'un événement extraordinaire susceptible d'expliquer une détérioration rapide du lien conjugal, soit l'absence de conscience de la gravité de ses problèmes de couple et, ainsi, l'existence d'une véritable volonté de maintenir une union stable avec son conjoint lorsqu'il a signé la déclaration (<ref-ruling> consid. 3 p. 165 s. et les arrêts cités).
2.2. En l'espèce, le Tribunal administratif fédéral a constaté que le recourant avait signé la déclaration de vie commune le 22 juillet 2011, qu'il avait obtenu la naturalisation le 3 août 2011, que les ex-époux avaient commencé à envisager une séparation en avril 2012 - après que le recourant avait rencontré dans son pays d'origine une jeune compatriote (de 38 ans plus jeune que son épouse) -, qu'ils s'étaient séparés en septembre 2012, qu'ils avaient déposé une requête commune en divorce avec accord complet sur les effets accessoires le 7 janvier 2013 et que leur union avait été dissoute par jugement du 8 mars 2013.
L'instance précédente pouvait donc, à juste titre, considérer que l'enchaînement chronologique de ces éléments,en particulier la séparation intervenue moins de 12 mois après l'entrée en force de la décision d'octroi de la naturalisation facilitée, était de nature à fonder la présomption que celle-ci avait été obtenue frauduleusement (cf. notamment arrêts du Tribunal fédéral 1C_796/2013 du 13 mars 2014 consid. 3.2 et 1C_172/2012 du 11 mai 2012 consid. 2.3). Contrairement à ce que pense le recourant, l'instance précédente n'a pas basé son appréciation sur la différence d'âge entre les ex-époux; la présomption de fait repose en effet sur l'enchaînement chronologique des éléments énumérés ci-dessus. Cette présomption apparaît en outre renforcée par le remariage de l'intéressé avec une compatriote à peine deux mois après le prononcé du divorce.
Conformément à la jurisprudence précitée (consid. 2.1.2), il s'agit donc uniquement de déterminer si l'intéressé est parvenu à renverser cette présomption.
2.3. Selon le recourant, sa rencontre subite avec une jeune compatriote constituerait un événement extraordinaire ayant conduit à la séparation du couple. Il affirme qu'avant cet événement, la communauté conjugale qu'il formait avec son ex-épouse était stable, intacte et tournée vers l'avenir, comme l'attesteraient les déclarations de son ex-épouse et divers témoignages. Il soutient que la séparation n'avait pas été facile et qu'elle n'était intervenue qu'après plusieurs mois de discussions, en l'occurrence six mois environ après sa rencontre avec sa future épouse.
Les explications du recourant ne sont toutefois pas convaincantes et ne permettent pas de renverser la présomption établie. L'instance précédente pouvait en l'espèce, sans violer le droit fédéral, considérer que la rencontre du recourant avec une jeune compatriote ne présentait aucun caractère imprévu et extraordinaire, mais apparaissait en réalité comme un événement attendu et accepté à l'avance par les époux qui allait entraîner leur séparation. Il ressort en particulier des déclarations de son ex-épouse que les intéressés étaient conscients que leur union n'était que de nature temporaire et prendrait fin lorsque le recourant rencontrerait une jeune femme avec laquelle il déciderait de fonder une famille (" j'avais envie de vivre cette expérience tout en sachant que cette histoire s'arrêterait le jour où A._ aurait envie de fonder une famille " et " je savais que j'allais céder ma place à une plus jeune femme "). Cette appréciation paraît en outre confirmée par le fait que cette rencontre avec sa future épouse algérienne est intervenue quelques mois seulement après l'entrée en force de la décision d'octroi de la naturalisation facilitée. Il est par ailleurs peu vraisemblable que les ex-époux, s'ils formaient réellement un couple effectif et stable, n'aient pas tenté d'une manière ou d'une autre de sauver leur union conjugale et qu'ils aient aussi rapidement accepté l'idée d'une séparation définitive.
Le recourant fait encore grief à l'instance précédente de ne pas s'être préoccupée des faits ayant précédé son premier mariage; il fait notamment valoir que leur couple avait vécu une relation intense de plus d'une année avant de se marier et que les enfants de son ex-épouse (témoins de mariage) avaient donné leur accord à cette union. Ces éléments ne permettent cependant pas d'établir qu'au moment de la signature de la déclaration commune, l'harmonie existait toujours au sein du couple au point d'envisager la continuation de la vie commune. Les déclarations écrites de tiers censés confirmer le sérieux de la communauté conjugale des intéressés ne permettent pas non plus d'affaiblir la présomption établie. N'est par ailleurs pas déterminant le fait que ce soit son ex-épouse qui l'ait encouragé à entreprendre la procédure de naturalisation facilitée. Enfin, le fait que le recourant ait gardé de bons contacts avec son ex-épouse, qu'il ait divorcé de sa compatriote et qu'il soit bien intégré en Suisse est sans pertinence pour apprécier si la naturalisation a été obtenue de façon frauduleuse ou non.
Il en découle que les conditions d'application de l'art. 41 LN sont réunies et que le Tribunal administratif fédéral n'a pas violé le droit fédéral en confirmant l'annulation de la naturalisation facilitée qui avait été octroyée au recourant.
3.
Les considérants qui précèdent conduisent au rejet du recours, aux frais du recourant qui succombe (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Secrétariat d'Etat aux migrations et au Tribunal administratif fédéral, Cour III.
Lausanne, le 27 octobre 2015
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Fonjallaz
La Greffière : Arn