\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}          % les bons codes pour les bonnes lettres
\usepackage{listings}% pour les listings informatiques
\usepackage[frenchb]{babel}
\usepackage{keystroke}% pour les touches du clavier
\usepackage{amsmath,amsfonts,amsthm,geometry,pst-all}
\usepackage{amssymb}
\geometry{a4paper,left=1cm,right=1cm,top=1cm,bottom=1cm,noheadfoot}
\usepackage{pifont}
\usepackage{graphicx}
%\usepackage{yhmath} %pour faire un arc de cercle $\wideparen{AB}$ 
\usepackage{eurosym} % pour avoir le symbole euro \euro
\pagestyle{empty}
\setlength{\parindent}{0cm}
\usepackage{multicol}
\usepackage{slashbox} %pour barrer une cellule d'un tableau
\usepackage{color}
\usepackage{mathrsfs, wasysym} % mathscfs donne accès aux lettres curvilignes
\usepackage{pstricks,pstricks-add,pst-math,pst-xkey} % packages utiles pour le pstricks
\usepackage{multirow,colortbl,tabularx} % packages utilisés dans un tableau (tabular)
\usepackage{array}
\usepackage{calc,fp}
\usepackage[french]{varioref}

\makeatletter
\define@key[psset]{}{transpalpha}{\pst@checknum{#1}\pstranspalpha}
\psset{transpalpha=1}
\def\psfs@transp{%
  \addto@pscode{/Normal .setblendmode \pstranspalpha .setshapealpha }%
  \psfs@solid}
%%%%%%%%%%%%%%%%%%%%%%%%%% Ceci sert lorsqu'on remplit une figure géométrique

\newcounter{numero}
\newcommand{\partie}{
\addtocounter{numero}{1}%
\textbf{\psframebox*[fillcolor=black!60]{\textbf{\white Partie \arabic{numero}:}}}\quad}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% incrémente le numéro de la partie

\setlength\leftmargini{0.73cm}
\renewcommand{\labelenumi}{\psframebox*[fillcolor=black!25]{\textbf{\white{\arabic{enumi}.}}}}
\setlength\leftmarginii{0.40cm}
\renewcommand{\labelenumii}{\textbf{\alph{enumii}.}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% définition des items

\newcounter{degradecadre}
\newcounter{ptinit}
\newcounter{ptfin}
\newcounter{ycadreinit}
\newcounter{ycadrefin}
\newcommand{\cadre}[2]{\begin{pspicture}(0,0)(19,1.4)
	\multido{\i=1+1}{16}{
		\multido{\n=1+1}{2}{
			\FPeval{\degradecadre}{90-\i*4}
			\FPeval{\ptinit}{1.1875*(\i-1)}
			\FPeval{\ptfin}{1.1875*(\i-1)+1.1875}
			\FPeval{\ycadreinit}{(\n-1)*1.4}
			\FPeval{\ycadrefin}{(\n-1)*1.4+0.1}
			\psframe[fillstyle=solid,fillcolor=black!\degradecadre,linestyle=none](\ptinit,\ycadreinit)(\ptfin,\ycadrefin)}}
	\psframe[fillstyle=solid,fillcolor=black!90,linestyle=none](0,0)(0.1,1.4)
	\psframe[fillstyle=solid,fillcolor=black!26,linestyle=none](18.9,0)(19,1.4)
	\rput(9.5,1){#1} \rput(9.5,0.4){#2}
\end{pspicture}\par}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% cadre et titre

\newcounter{degrade}
\newcounter{ptdepart}
\newcounter{ptfinal}
\def\lignetirets{\begin{pspicture}(0,0)(19,0.2)
	\multido{\i=1+1}{16}{
		\FPeval{\degrade}{90-\i*4}
		\FPeval{\ptdepart}{1.2*(\i-1)}
		\FPeval{\ptfinal}{1.2*(\i-1)+1}
		\psframe[fillstyle=solid,fillcolor=black!\degrade,linestyle=none](\ptdepart,0)(\ptfinal,0.2)}
\end{pspicture}\par}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ligne tirets

\renewcommand\rmdefault{phv}

\newcommand{\procedure}[3]{
	\setlength{\arrayrulewidth}{1.8pt}
	\begin{tabularx}{#1}[t]{|X}
		\rowcolor[gray]{0.6}
		\textcolor{white}{#2}\\ 
		\cellcolor{gray!20}
		#3\\
	 \hline
	\end{tabularx}
	\setlength{\arrayrulewidth}{0.6pt}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% crée les cadres pour Procédure; en paramètre, on met le texte

\def\R{{\mathbb R}} % les réels
\def\Q{{\mathbb Q}} % les rationnels
\def\Z{{\mathbb Z}} % les entiers relatifs
\def\D{{\mathbb D}} % les décimaux
\def\N{{\mathbb N}} % les entiers naturels
\def\C{{\mathbb C}} % les complexes
\def\c{{\mathscr C}} % pour les courbes
\def\Pl{\mathscr{P}} % pour les plans
\def\Oij{$\left(O;~\vec{i},~\vec{j}\right)$} % pour nommer un repère (O;i,j)
\def\cad{c'est-à-dire}
\def\e{\mathrm{e}} %pour écrire correctement le nombre e
\def\i{\mathrm{i}} %pour écrire correctement le nombre i
\def\d{\,\text{d}} % pour avoir un "d" droit dans l'intégrale

\newcommand{\ve}[1]{\overrightarrow{#1}} %pour les vecteurs
\newcommand{\Cnp}[2]{\displaystyle{{#1 \choose #2}}} % pour les p parmi n
\newcommand{\systeme}[2]{\left\{\begin{array}{l}
	#1\\
	#2\\
\end{array}\right.} % pour créer un système de deux équations

\makeatletter
\newlength{\@longarc}
\newcommand{\arc}[1]{\settowidth{\@longarc}{$#1$}
	\addtolength{\@longarc}{-0.2em}
	\unitlength \@longarc
	\ensuremath{
		\stackrel{\begin{picture}(1,0.2)
			\qbezier(0,0)(0.5,0.2)(1,0)
		\end{picture}}
		{#1}
	}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%   Pour les listings de code et les réponses du logiciel


\usepackage{bold-extra,fancyvrb}
\usepackage[scaled=0.85]{luximono}
\DefineVerbatimEnvironment{boxedverbatim}{Verbatim}{gobble=2,frame=single,framesep=4mm,label=\textit{\small
    Réponse du logiciel}}

\definecolor{0.9white}{rgb}{0.9,0.9,0.9}
\definecolor{0.2white}{rgb}{0.2,0.2,0.2}


\lstloadlanguages{XCAS}
\lstset{numbers=none,language=XCAS,xleftmargin=10pt,%
keywordstyle =\color{0.2white}\bfseries\usefont{OT1}{cmtt}{b}{n},basicstyle=\ttfamily,commentstyle=\normalfont\scriptsize\itshape,%\small,
    backgroundcolor=\color{0.9white},breaklines=true}
   

\newcommand\Prog[1]{{\bfseries\ttfamily #1}}

\newcommand{\code}[1]{\texttt{#1}}



%%%%%%%%%%%%%%%%%%%%% pour créer un arc de cercle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Début du document %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}
\setlength{\unitlength}{1mm}

\cadre{\LARGE \emph{TEST DE PRIMALITÉ}}{\Large \emph{Un doigt d'algorithmique...}}



\textbf{Compétences mathématiques\::}\par
	\hspace{1cm} $\bullet$ Division euclidienne, définition d'un nombre premier

\textbf{Compétences informatiques\::}\par
	\hspace{1cm} $\bullet$ test «~SI~», boucle «~TANT QUE~». Notion d'efficacité d'un algorithme.

\textbf{Prérequis\::}\par
	\hspace{1cm} $\bullet$ Avoir manipulé les tests et les boucles.

\lignetirets


\partie \textbf{Mise au point théorique du test}\\
\procedure{\linewidth}{Le problème}{On veut créer une procédure qui teste si un entier donné est
  premier ou non. }

\begin{enumerate}
\item \textbf{Simplification du problème}\\

Une première idée pour tester la primalité d'un nombre donné $a$ est de le diviser successivement
par tous les entiers supérieurs à 2 plus petits que lui.

\begin{enumerate}
\item Quand pourra-t-on conclure que le nombre est premier~?
\item Pourquoi suffit-il de diviser par les entiers inférieurs à $\sqrt{a}$~?
\end{enumerate}


\item \textbf{Division euclidienne}\\

\Prog{XCAS} dispose d'une fonction \code{reste(n,p)} qui renvoie le reste de la division euclidienne
de $n$ par $p$. En quoi peut-elle nous être utile pour résoudre notre problème~?

\end{enumerate}


\partie\label{analyse} \textbf{Analyse de l'algorithme}\\


  \begin{enumerate}
  \item\label{si1} On rentre un nombre $a$ : que faire si ce nombre est pair~? Pourquoi se pose-t-on cette
    question~? S'il n'est pas pair, on continue.
  \item Si on prend les entiers dans l'ordre
croissant, par lequel va-ton continuer  à tester $a$ d'après nos remarques
faites à la question 1. ?  Notons j cet entier. Tant que cet entier reste
    inférieur à $\sqrt{a}$, on va tester s'il divise $a$. Si oui, que fait-on~?
\item Sinon, regarde-t-on l'entier suivant~?
\item Si on finit par dépasser $\sqrt{a}$ sans que nos différents $j$ n'aient divisé
$a$~:~que peut-on en conclure~?

 \end{enumerate}

% \begin{figure}[h]

% % \ovalnode{E}{Entrer $a$}
% % \hspace*{1cm}
% % \dianode{Pair}{\code{reste(a,2)==0}}\vspace*{-1cm}\pnode{Oui1}{(1)}
% % \ncline{->}{E}{Pair}
% % \ncline{->}{Pair}{Oui1}\nbput{oui}


% $\pstree{\Toval{\code{Entrer a}}}{\pstree{\Tdia{\code{reste(a,2)==0}}}{\pstree{\Toval{3\leftarrow
%         J}^{non}}{\pstree{\Toval{J+2\leftarrow J}}{\pstree{\Tdia{J\times J>a}}{\pstree{\Tdia{\code{reste(a,J)==0}}^{non}}{{\Tr{(4)}^{non}}{\Tr{(3)}_{oui}}}{\Tr{(2)}_{oui}}}}}{\Tr{(1)}_{oui}}}}
% $


% \end{figure}

% \item \textbf{Analyse de l'algorithme}
% \begin{enumerate}
% \item Que peut-on dire sur $a$ dans chacun des cas (1), (2) et (3)~?
% \item Pourquoi fait-on faire des «~sauts~» de deux unités à J~?
% \item Où va la dernière flèche qui part de (4)~? 
% \end{enumerate}

% \end{enumerate}









\partie \textbf{Écriture de l'algorithme}\\

Nous allons appeler notre procédure \code{test\_premier(a)}.

\begin{enumerate}
\item À quel sorte de test correspond le problème évoqué à la question \vref{si1} de la partie 2~?
\item Quels autres tests ont été évoqués dans les questions suivantes~?
\item Écrivez la procédure en utilisant les mots-clés suivants~:~\code{tantque}, \code{return},
  \code{si...alors...sinon}, \code{reste}.
\end{enumerate}


\partie \textbf{Efficacité de l'algorithme}

\begin{enumerate}
\item Testons notre test... sur 42, 43, 143, 12345678910111213141516171819.
\item Plus dur~:~10000030019000057 est-il premier~?
\item Essayez de trouver un grand nombre premier (au moins 10 chiffres).
\item Comment trouver un grand nombre premier d'au moins 20 chiffres~? \Prog{XCAS} peut nous y aider
  avec la commande \code{nextprime(n)} qui donne le premier nombre premier qui suit n.

Que donne \code{test\_premier(nextprime(10\textasciicircum 20))}~? 

Si vous trouvez le temps trop long, n'hésitez pas à cliquer sur \keystroke{STOP}...

Notre procédure est en fait très peu efficace. Il faut savoir que la manipulation des nombres
premiers de plus de 200 chiffres est à la base de la sécurité des messages sur internet, des
transactions bancaires, etc.

\Prog{XCAS} a son propre test de primalité noté \code{isprime}. Que donne~:

\begin{lstlisting}
  isprime(nextprime(10^100))
\end{lstlisting}

Quel a été le temps de calcul. Il nous reste beaucoup de chemin à parcourir pour être capable d'être
aussi efficace... 
\end{enumerate}




\partie \textbf{Application~:~recherche des nombres chanceux}\\

\procedure{\linewidth}{Nouveau problème}{Soit l'algorithme suivant~:
  \begin{itemize}
  \item choisir un entier naturel;
  \item l'élever au carré;
  \item ajouter au résultat le nombre initialement choisi;
  \item à ce dernier ajouter 41;
  \item lire ce dernier résultat.
  \end{itemize}
Qu'observe-t-on~? Et si on prend un autre nombre que 41~?
}

\begin{enumerate}
\item Écrire l'algorithme à l'aide de \Prog{XCAS}.
\item Si on part de 0, jusqu'à quand obtient-on des nombres premiers~?
(On pourra utiliser notre test des parties précédentes ou \code{isprime}).
\item Essayez avec d'autres nombres premiers plus petits que 41.
\item Commentez ces procédures~:

  \begin{lstlisting}
test_court_premier(a):={
si reste(a,2)==0 alors return(0);
sinon j:=3;
   tantque  j*j<=a faire
        si reste(a,j)==0 alors return(0);
        sinon j:=j+2;
        fsi
   ftantque
   return(1);
fsi
}:; 
  \end{lstlisting}

Puis

\begin{lstlisting}
test_chanceux(X):={
local t;
t:=0;
tantque test_court_premier(chanceux(t,X))==1 faire t:=t+1;
ftantque
si t>=X-2 alors return(1); sinon return(0);
fsi
}:;
\end{lstlisting}


et enfin

\begin{lstlisting}
recherche_chanceux(x):={
Liste:=NULL;
pour k de 2 jusque x faire
  si test_chanceux(k)==1 alors Liste:=Liste,k;
  fsi
fpour
Liste
}:;
\end{lstlisting}

\end{enumerate}




\end{document}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
