12SN/A/* 21762SN/A * Copyright (c) 2001, 2003-2005 The Regents of The University of Michigan 32SN/A * All rights reserved. 42SN/A * 52SN/A * Redistribution and use in source and binary forms, with or without 62SN/A * modification, are permitted provided that the following conditions are 72SN/A * met: redistributions of source code must retain the above copyright 82SN/A * notice, this list of conditions and the following disclaimer; 92SN/A * redistributions in binary form must reproduce the above copyright 102SN/A * notice, this list of conditions and the following disclaimer in the 112SN/A * documentation and/or other materials provided with the distribution; 122SN/A * neither the name of the copyright holders nor the names of its 132SN/A * contributors may be used to endorse or promote products derived from 142SN/A * this software without specific prior written permission. 152SN/A * 162SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Nathan Binkert 292665Ssaidi@eecs.umich.edu * Steve Reinhardt 302SN/A */ 312SN/A 3256SN/A#include "base/intmath.hh" 332SN/A 342SN/Aint 352020SN/AprevPrime(int n) 362SN/A{ 372020SN/A int decr; 382SN/A 392020SN/A // If the number is even, let's start with the previous odd number. 402020SN/A if (!(n & 1)) 412020SN/A --n; 422SN/A 432020SN/A // Lets test for divisibility by 3. Then we will be able to easily 442020SN/A // avoid numbers that are divisible by 3 in the future. 452020SN/A decr = n % 3; 462020SN/A if (decr == 0) { 472020SN/A n -= 2; 482020SN/A decr = 2; 492020SN/A } 502020SN/A else if (decr == 1) 512020SN/A decr = 4; 522SN/A 532020SN/A for (;;) { 542020SN/A if (isPrime(n)) 552020SN/A return n; 562020SN/A n -= decr; 572020SN/A // Toggle between 2 and 4 to prevent trying numbers that are known 582020SN/A // to be divisible by 3. 592020SN/A decr = 6 - decr; 602020SN/A } 612SN/A} 62