intmath.cc revision 56
12124SN/A/* 22124SN/A * Copyright (c) 2003 The Regents of The University of Michigan 35268Sksewell@umich.edu * All rights reserved. 45268Sksewell@umich.edu * 55268Sksewell@umich.edu * Redistribution and use in source and binary forms, with or without 65268Sksewell@umich.edu * modification, are permitted provided that the following conditions are 75268Sksewell@umich.edu * met: redistributions of source code must retain the above copyright 85268Sksewell@umich.edu * notice, this list of conditions and the following disclaimer; 95268Sksewell@umich.edu * redistributions in binary form must reproduce the above copyright 105268Sksewell@umich.edu * notice, this list of conditions and the following disclaimer in the 115268Sksewell@umich.edu * documentation and/or other materials provided with the distribution; 125268Sksewell@umich.edu * neither the name of the copyright holders nor the names of its 135268Sksewell@umich.edu * contributors may be used to endorse or promote products derived from 145268Sksewell@umich.edu * this software without specific prior written permission. 155268Sksewell@umich.edu * 165268Sksewell@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175268Sksewell@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185268Sksewell@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195268Sksewell@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205268Sksewell@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215268Sksewell@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225268Sksewell@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235268Sksewell@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245268Sksewell@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255268Sksewell@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265268Sksewell@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275268Sksewell@umich.edu */ 285268Sksewell@umich.edu 295268Sksewell@umich.edu#include "base/intmath.hh" 305268Sksewell@umich.edu 312022SN/Aint 322649Ssaidi@eecs.umich.eduPrevPrime(int n) 332649Ssaidi@eecs.umich.edu{ 342706Sksewell@umich.edu int decr; 352649Ssaidi@eecs.umich.edu 362649Ssaidi@eecs.umich.edu // If the number is even, let's start with the previous odd number. 372022SN/A if (!(n & 1)) 382124SN/A --n; 392124SN/A 402124SN/A // Lets test for divisibility by 3. Then we will be able to easily 412124SN/A // avoid numbers that are divisible by 3 in the future. 422124SN/A decr = n % 3; 432124SN/A if (decr == 0) { 442124SN/A n -= 2; 455736Snate@binkert.org decr = 2; 462239SN/A } 472124SN/A else if (decr == 1) 482124SN/A decr = 4; 492124SN/A 502124SN/A for(;;) { 516207Sksewell@umich.edu if (IsPrime(n)) 522124SN/A return n; 532742Sksewell@umich.edu n -= decr; 542022SN/A // Toggle between 2 and 4 to prevent trying numbers that are known 552124SN/A // to be divisible by 3. 562022SN/A decr = 6 - decr; 572124SN/A } 582124SN/A} 592124SN/A